Circumscribing Polygons and Polygonizations for Disjoint Line Segments

Autor: Hugo A. Akitaya, Matias Korman, Oliver Korten, Mikhail Rudoy, Diane L. Souvaine, Csaba D. Tóth
Rok vydání: 2022
Předmět:
Zdroj: Discrete & Computational Geometry. 68:218-254
ISSN: 1432-0444
0179-5376
DOI: 10.1007/s00454-021-00355-8
Popis: Given a planar straight-line graph $G=(V,E)$ in $\mathbb{R}^2$, a \emph{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 \emph{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 $\mathbb{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.
Comment: Extended version (preliminary abstract accepted in the proceedings of SoCG 2019)
Databáze: OpenAIRE
Externí odkaz: