2019/12/07 by Elias Dahlhaus, Sariel Har-Peled, Dahlhaus, Elias +3
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Optimization and Packing Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1912.03429
openalex publication_date 2019/12/07 · arxiv created 2019/12/10 · arxiv updated 2019/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set of disjoint simple polygons σ1, …, σn, of total complexity N, consider a convexification process that repeatedly replaces a polygon by its convex hull, and any two (by now convex) polygons that intersect by their common convex hull. This process continues until no pair of polygons intersect. We show that this process has a unique output, which is a cover of the input polygons by a set of disjoint convex polygons, of total minimum area. Furthermore, we present a near linear time algorithm for computing this partition. The more general problem of covering a set of N segments (not necessarily disjoint) by min-area disjoint convex polygons can also be computed in near linear time. A similar result is already known, see the work by Barba et al. [BBB+13].