Journal of the Association for Computing Machinery, Vol. 44, No. 1, January 1997, pp. 1–29.

Separators for Sphere-Packings and Nearest Neighbor Graphs

GARY L. MILLER

SHANG-HUA TENG

WILLIAM THURSTON

AND

STEPHEN A. VAVASIS

Abstract. A 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 Γ, there is a sphere S that intersects at most O(k^{1/d}n^{1−1/d}) balls of Γ and divides the remainder of Γ 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.

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

Copyright 1997 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.