2026-08-06T13:42:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10413 2024-03-06T10:45:55Z ddc:004 open_access

Circumscribing Polygons and Polygonizations for Disjoint Line Segments Akitaya, Hugo A. Korman, Matias Rudoy, Mikhail Souvaine, Diane L. Tóth, Csaba D. circumscribing polygon Hamiltonicity extremal combinatorics Given a planar straight-line graph G=(V,E) in R^2, a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P. We prove that every arrangement of n disjoint line segments in the plane has a subset of size Omega(sqrt{n}) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R^3. We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Matias Korman and Mikhail Rudoy and Diane L. Souvaine and Csaba D. Tóth 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.9 urn:nbn:de:0030-drops-104136 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.9 eng https://creativecommons.org/licenses/by/3.0/legalcode