Given a set $S$ of $n$ points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of $S$. Previously, Eppstein [SODA97] gave a randomized algorithm of $O(nlog^2n)$ expected time and Chan [CGTA99] presented a deterministic algorithm of $O(nlog^2 nlog^2log n)$ time. In this paper, we propose an $O(nlog^2 n)$ time deterministic algorithm, which improves Chans deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(nlog nloglog n)$ deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.
Download