The Two-Center Problem for Convex Polygons

Abstract

In this thesis, we consider the planar two-center problem for a convex polygon: given a convex polygon in the plane, fi nd two congruent disks of minimum radius whose union contains the polygon. For a convex polygon P with n vertices, we present an O(n log n)-time algorithm for the two-center problem for P. This improves upon the previously best known algorithm for the problem.