Faster construction of planar two-centers
David Eppstein · eScholarship (California Digital Library) · 1997
Improving on a recent breakthrough of Sharir, we find two minimum-radius circular disks covering a planar point set, in randomized expected time O(n log 2 n). 1 Introduction The k-center problem for a point set S is to find k points (called centers, usually not required to be a subset of S) such that the maximum distance from any point in S to the nearest center is minimized. A case of particular interest is the planar two-center problem [4], which can be viewed less abstractly as one of covering a set of points in the plane by two congruent circular disks, in such a way as to minimize the radius r # of the disks. For a long time the best algorithms for this problem had time bounds of the form O(n 2 log c n) [1, 5, 12, 11]. In a recent breakthrough, Sharir [16] greatly improved all of these algorithms, giving a two-center algorithm with running time O(n log c n). The basic idea is to search for different types of partition depending on the relative positions of the two disk...