Efficient Planar Two-Center Algorithms
share
We consider the planar Euclidean two-center problem in which given n points in the plane we are to find two congruent disks of the smallest radius covering the points. We present a deterministic O(n log n)-time algorithm for the case that the centers of the two optimal disks are close to each other, that is, the overlap of the two optimal disks is a constant fraction of the disk area. We also present a deterministic O(nlog n)-time algorithm for the case that the input points are in convex position. Both results improve the previous best O(nlog nloglog n) bound on the problems.
READ FULL TEXT