Abstract.
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].
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received May 2, 1995, and in revised form July {8, 1995}.
Rights and permissions
About this article
Cite this article
Sharir, M. A Near-Linear Algorithm for the Planar 2-Center Problem . Discrete Comput Geom 18, 125–134 (1997). https://doi.org/10.1007/PL00009311
Issue Date:
DOI: https://doi.org/10.1007/PL00009311