Covering Convex Polygons by Two Congruent Disks

2021/05/06 by Jongmin Choi, Choi, Jongmin, Dahye Jeong +3
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2105.02483

openalex publication_date 2021/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the planar two-center problem for a convex polygon: given a convex polygon in the plane, find two congruent disks of minimum radius whose union contains the polygon. We present an O(nlog n)-time algorithm for the two-center problem for a convex polygon, where n is the number of vertices of the polygon. This improves upon the previous best algorithm for the problem.

Related

• Approximation algorithms for the two-center problem of convex polygon
• Efficient Planar Two-Center Algorithms
• On the Planar Two-Center Problem and Circular Hulls
• Covering and Piercing Disks with Two Centers
• Efficient covering of convex domains by congruent discs