A Near-Linear Algorithm for the Planar 2-Center Problem

Authors: Micha Sharir - Discrete & Computational Geometry 1996 cited by 89

We present an \(O(n\log^{9}n)\) -time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent disks of smallest radius whose union covers S), improving the previous \(O(n^2\log n)\) -time algorithm of [10].