Cover Ratio of Absolute Neighbor.

Voronoi diagrams for a fix set of generators are considered with varying Lp norm. For a generator q in the set, the absolute neighbor of q is defined to be the intersection of all Voronoi regions of q by Lp norm(p = 1, 2..., ∞). Since the shape of Voronoi region is dependent on the norm used, the collection of absolute neighbors for the set does not always cover the whole space. In this paper, we construct absolute neighbors and computed the ratio, called cover ratio, of the volume covered by all absolute neighbors to that of the whole space for some sets of generators by computational experiments. Computational experiments show that the cover ratio is higher when a configuration of grid points is used as a set of generators than when a set of random generators is used. Moreover, we theoretically show that the absolute neighbors for square configuration and for face-centered configuration cover the whole space. We also discuss an application of absolute neighbors to constructing an index structure of the whole space for efficient retrieval. [ABSTRACT FROM AUTHOR]