Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.9
URN: urn:nbn:de:0030-drops-169470
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16947/
Antoniadis, Antonios ; de Berg, Mark ; Kisfaludi-Bak, Sándor ; Skarlatos, Antonis
Computing Smallest Convex Intersecting Polygons
| pdf-format: |
|
Abstract
A polygon C is an intersecting polygon for a set O of objects in ℝ² if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n.Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.
BibTeX - Entry
@InProceedings{antoniadis_et_al:LIPIcs.ESA.2022.9,
author = {Antoniadis, Antonios and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Skarlatos, Antonis},
title = {{Computing Smallest Convex Intersecting Polygons}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {9:1--9:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16947},
URN = {urn:nbn:de:0030-drops-169470},
doi = {10.4230/LIPIcs.ESA.2022.9},
annote = {Keywords: convex hull, imprecise points, computational geometry}
}
| Keywords: | convex hull, imprecise points, computational geometry | |
| Seminar: | 30th Annual European Symposium on Algorithms (ESA 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 01.09.2022 |
