A deterministic linear time algorithm for geometric separators and its applications

We give a deterministic linear time algorithm for finding a small cost sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in Rd is a collection of n balls such that no points in the space is covered by more than k balls. The sphere separator intersects at most O (k1/2 nd-1/d) balls of Φ and it 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 [29] and answers a major algorithmic open question posed by Mille, Teng,Thurston and Vavasis [23,25].