A DETERMINISTIC LINEAR TIME ALGORITHM FOR GEOMETRIC SEPARATORS AND ITS APPLICATIONS

Article type: Research Article

Authors: Eppstein, David | Miller, Gary L. | Teng, Shang-Hua

Affiliations: Department of Information and Computer Science, University of California, Irvine, CA 92717 | School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 | Department of Mathematics and Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139

Abstract: We give a deterministic linear time algorithm for finding a “good” sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in $\IR$d is a collection of n balls such that no points in the space is covered by more than k balls. The separating sphere intersects at most O (k1/dn1−1/d) balls of Φ and divides the remaining of Φ into two parts: those in the interior and those in the exterior of the sphere, respectively, so that the larger part contains at most δn balls ((d + 1)/(d + 2) < δ < 1). This result improves the O(n2) time deterministic algorithm of Miller and Teng [30] and answers a major algorithmic open question posed by Miller, Teng, Thurston, and Vavasis [23, 26]. The deterministic algorithm hinges on the use of a new method for deriving the separator property of neighborhood systems. Using this algorithm, we devise an O(kn+nlogn) time deterministic algorithm for computing the intersection graph of a k-ply neighborhood system. We give an O(nlogn) time algorithm for constructing a linear space, O(logn) query time search structure for a geometric query problem associated with k-ply neighborhood systems, and we use this data structure in an algorithm for approximating the value of k within a constant factor in time O(nlogn). We also develop a deterministic linear time algorithm for finding an O (k1/dn1−1/d)-separator for a k-nearest neighborhood graph in d dimensions.

DOI: 10.3233/FI-1995-2241

Journal: Fundamenta Informaticae, vol. 22, no. 4, pp. 309-329, 1995