Linear-size approximate voronoi diagrams

ABSTRACT

Given a set S of n points in IR^d, a (t, ε)-approximate Voronoi diagram (AVD) is a partition of space into constant complexity cells, where each cell c is associated with t representative points of S, such that for any point in c, one of the associated representatives approximates the nearest neighbor to within a factor of (1 + ε). The goal is to minimize the number and complexity of the cells in the AVD. We show that it is possible to construct an AVD consisting of O(n/ε^d) cells for t = 1, and O(n) cells for t = O(1/ε^(d-1)/2). In general, for a real parameter 2 ≤ γ ≤ 1/ε, we show that it is possible to construct a (t, ε)-AVD consisting of O(nγ^d) cells for t = O(1/(εγ)^(d-1)/2). The cells in these AVDs are cubes or differences of two cubes. All these structures can be used to efficiently answer approximate nearest neighbor queries. Our algorithms are based on the well-separated pair decomposition and are very simple.

REFERENCES

• 1: S. Arya, T. Malamatos, and D. M. Mount. Manuscript, in preparation.
• 2: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 3: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 4: T. M. Chan. Approximate nearest neighbor queries revisited. Discrete Comput. Geom., 20:359-373, 1998.
• 5: T. M. Chan and J. Snoeyink. Algorithms for approximate nearest-neighbor queries. Manuscript, 1995.
• 6: Christian A. Duncan , Michael T. Goodrich , Stephen Kobourov, Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.300-309, January 17-19, 1999, Baltimore, Maryland, United States
• 7: S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
• 8: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 9: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
• 10: J. S. B. Mitchell, D. M. Mount, and S. Suri. Query-sensitive ray shooting. Internat. J. Comput. Geom. Appl., 7(4):317-347, August 1997.
• 11: Y. Sabharwal, S. Sen, and N. Sharma. Improved space bound for approximate Voronoi diagram. Manuscript, 2001.
• 12: J. Vleugels and M. Overmars. Approximating Voronoi diagrams of convex sites in any dimension, Internat. J. Comput. Geom. Appl., 8:201-222, 1998.
• 13: A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721-736, 1982.