The Discrete 2-Center Problem

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P , whose union covers P . Our algorithm runs in time O(n 4=3 log 5 n). 1 Introduction Problem statement and previous results. Let P be a set of n points in the plane. The discrete 2-center problem for P is to cover P by (the union of) two congruent closed disks whose radius is as small as possible, and whose centers are two points of P . This is a restricted version of the standard 2-center problem, where the centers of the two covering disks can be any pair of points in the plane. This latter problem has been studied extensively, where the best algorithm, due to Sharir [14] and slightly improved by Eppstein [6], runs in randomized expected O(n log 2 n) time. The discrete 2-center problem has been studied in [7], where a near-quadratic algorithm is proposed (such an algorithm is briefly..