Separators for sphere-packings and nearest neighbor graphs

TLDR

A k‑ply system of n balls in d dimensions is defined as a collection where no point is covered by more than k balls. The study proposes a simple randomized algorithm that finds such a sphere separator in linear time. The algorithm runs in O(n) time by selecting a sphere that intersects at most O(k^{1/d} n^{1-1/d}) balls and partitions the remaining balls into interior and exterior subsets. The authors prove that every k‑ply system admits a sphere separator intersecting at most O(k^{1/d} n^{1-1/d}) balls, that this bound is optimal, and that it yields a separator of the same size for k‑nearest neighbor graphs, thereby extending the planar separator theorem to higher dimensions.

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.