A near-linear algorithm for the Planar 2-center problem

A near-linear algorithm for the Planar 2-center problem

0.00 Avg rating0 Votes
Article ID: iaor19981402
Country: United States
Volume: 18
Issue: 2
Start Page Number: 125
End Page Number: 134
Publication Date: Sep 1997
Journal: Discrete and Computational Geometry
Authors:
Keywords: location
Abstract:

We present an O(n log9 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(n2 log n)-time algorithm.

Reviews

Required fields are marked *. Your email address will not be published.