### Separators for sphere-packings and nearest neighbor graphsSeparators for sphere-packings and nearest neighbor graphs

Access Restriction
Subscribed

 Author Miller, Gary L. ♦ Teng, Shang-Hua ♦ Thurston, William ♦ Vavasis, Stephen A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1997 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Centerpoint ♦ Computational geometry ♦ Graph algorithms ♦ Graph separators ♦ Partitioning ♦ Point location ♦ Probabilistic method ♦ Rndomized algorithm ♦ Sphere-preserving mapping Abstract A collection of $\textit{n}$ balls in $\textit{d}$ dimensions forms a $\textit{k}-ply$ system if no point in the space is covered by more than $\textit{k}$ balls. We show that for every $\textit{k}-ply$ system Γ, there is a sphere $\textit{S}$ that intersects at most $\textit{O}(\textit{k}1/\textit{d}\textit{n}1™1/\textit{d})$ balls of Γ and divides the remainder of Γ into two parts: those in the interior and those in the exterior of the sphere $\textit{S},$ respectively, so that the larger part contains at most $(1™1/(\textit{d}+2))\textit{n}$ balls. This bound of $(\textit{O}(\textit{k}1/\textit{d}\textit{n}1™1/\textit{d})$ is the best possible in both $\textit{n}$ and $\textit{k}.$ We also present a simple randomized algorithm to find such a sphere in $\textit{O(n)}$ time. Our result implies that every $\textit{k}-nearest$ neighbor graphs of $\textit{n}$ points in $\textit{d}$ dimensions has a separator of size $\textit{O}(\textit{k}1/\textit{d}\textit{n}1™1/\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1997-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 44 Issue Number 1 Page Count 29 Starting Page 1 Ending Page 29

#### Open content in new tab

Source: ACM Digital Library