Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.9
URN: urn:nbn:de:0030-drops-104136
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10413/
Akitaya, Hugo A. ; Korman, Matias ; Rudoy, Mikhail ; Souvaine, Diane L. ; Tóth, Csaba D.
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{akitaya_et_al:LIPIcs:2019:10413,
author = {Hugo A. Akitaya and Matias Korman and Mikhail Rudoy and Diane L. Souvaine and Csaba D. T{\'o}th},
title = {{Circumscribing Polygons and Polygonizations for Disjoint Line Segments}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {9:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10413},
URN = {urn:nbn:de:0030-drops-104136},
doi = {10.4230/LIPIcs.SoCG.2019.9},
annote = {Keywords: circumscribing polygon, Hamiltonicity, extremal combinatorics}
}
| Keywords: | circumscribing polygon, Hamiltonicity, extremal combinatorics | |
| Seminar: | 35th International Symposium on Computational Geometry (SoCG 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 11.06.2019 |
