1997/01/15 by Gary L. Miller, Shang‐Hua Teng, William P. Thurston +1 · 223 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Point processes and geometric inequalities #Data Management and Algorithms #Combinatorics #Mathematics #Graph #Planar graph #Planar #SPHERES #Remainder #Computer science #Physics
paper · pdf · doi:10.1145/256292.256294
published in Journal of the ACM 44(1), 1-29 (Association for Computing Machinery)
openalex publication_date 1997/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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.