Linking disjoint axis-parallel segments into a simple polygon is hard too

2021/09/05 by Rain Jiang, Kai Jiang, Jiang, Rain +3
Computer Science · Engineering · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2109.02156

openalex publication_date 2021/09/05 · openalex created_date 2021/09/13 · openalex updated_date 2026/07/28

Abstract

Deciding whether a family of disjoint axis-parallel line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.

Related

• Linking disjoint segments into a simple polygon is hard
• Disjoint axis-parallel segments without a circumscribing polygon
• Computational Geometry Column 39
• Simply Realising an Imprecise Polyline is NP-hard
• Packing identical simple polygons is NP-hard