AbstractA collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system G, there is a sphere S that intersects at most O(k^{1/d} n^{1 - 1/d}) balls of G and divides the remainder of G into two parts: those in the interior and those in the exterior of the sphere S, respectively, so that the larger part contains at most (1 - 1/(d + 2))n balls. This bound of O(k^{1/d} n^{1 - 1/d}) is the best possible in both n and k. We also present a simple randomized algorithm to find such a sphere in O(n) time. Our result implies that every k-nearest neighbor graphs of n points in d dimensions has a separator of size O(k^{1/d} n^{1 - 1/d}). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: E.1 [Data Structures] -- graphs, trees; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems -- computation of transforms; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computaions on discrete structures, geometrical problems and computations, sorting and searching; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, trees; G.3 [Probability and Statistics] -- probabilistic algorithms, random number generation; G.4 [Mathematical Software] -- algorithm analysis, efficiency
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Centerpoint, computational geometry, graph algorithms, graph separators, partitioning, probabilistic method, point location, randomized algorithm, sphere-preserving mapping
Selected references
- Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 293-299, Baltimore, Maryland, 14-16 May 1990.
- Kenneth L. Clarkson. Fast algorithms for the all nearest neighbors problem. In 24th Annual Symposium on Foundations of Computer Science, pages 226-232, Tucson, Arizona, 7-9 November 1983. IEEE.
- Hubert de Fraysseix, János Pach, and Richard Pollack. Small sets supporting Fáry embeddings of planar graphs. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 426-433, Chicago, Illinois, 2-4 May 1988.
- A. Frieze, G. Miller, and S.-H. Teng. Separator based parallel divide and conquer in computational geometry. In Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, pages 420-430, San Diego, California, USA, June 1992. ACM Press.
- John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391-407, September 1984.
- Gary L. Miller and William Thurston. Separators in two and three dimensions. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 300-309, Baltimore, Maryland, 14-16 May 1990.
- Gary L. Miller, Shang-Hua Teng, and Stephen A. Vavasis. A unified geometric approach to graph separators. In 32nd Annual Symposium on Foundations of Computer Science, pages 538-547, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Gary L. Miller and Stephen A. Vavasis. Density graphs and separators. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 331-336, San Francisco, California, 28-30 January 1991.
- Serge Plotkin, Satish Rao, and Warren D. Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 462-470, Arlington, Virginia, 23-25 January 1994.