Approximation algorithms for the two-center problem of convex polygon

2015/12/08 by Sanjib Sadhu, Sasanka Roy, Sadhu, Sanjib +6
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1512.02356

openalex publication_date 2015/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a convex polygon P with n vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover P. We propose an algorithm for this problem in the streaming setup, where the input stream is the vertices of the polygon in clockwise order. It produces a radius r satisfying r≤2r_opt using O(1) space, where r_opt is the optimum solution. Next, we show that in non-streaming setup, we can improve the approximation factor by r≤ 1.84 r_opt, maintaining the time complexity of the algorithm to O(n), and using O(1) extra space in addition to the space required for storing the input.

Citations

• Packing and Covering a Polygon with Geodesic Disks

Related

• Covering Convex Polygons by Two Congruent Disks
• Efficient Planar Two-Center Algorithms
• On the Planar Two-Center Problem and Circular Hulls
• Covering and Piercing Disks with Two Centers
• Computing k-Centers On a Line