Access Restriction

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

   Open content in new tab
Source: ACM Digital Library