Computing Smallest Convex Intersecting Polygons

Antonios Antoniadis; Mark De Berg; Sándor Kisfaludi-Bak; Antonis Skarlatos

doi:10.4230/LIPIcs.ESA.2022.9

Computing Smallest Convex Intersecting Polygons

Antonios Antoniadis, Mark De Berg, Sándor Kisfaludi-Bak, Antonis Skarlatos

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

50 Downloads (Pure)

Abstract

A polygon C is an intersecting polygon for a set O of objects in R2 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.

Original language	English
Title of host publication	30th Annual European Symposium on Algorithms, ESA 2022
Editors	Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	13
ISBN (Electronic)	978-3-95977-247-1
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2022.9
Publication status	Published - 1 Sept 2022
MoE publication type	A4 Conference publication
Event	European Symposium on Algorithms - Berlin and Potsdam, Germany Duration: 5 Sept 2022 → 9 Sept 2022 https://algo2022.eu/esa/

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	244
ISSN (Print)	1868-8969

Conference

Conference	European Symposium on Algorithms
Abbreviated title	ESA
Country/Territory	Germany
City	Berlin and Potsdam
Period	05/09/2022 → 09/09/2022
Internet address	https://algo2022.eu/esa/

Keywords

computational geometry
convex hull
imprecise points

Access to Document

10.4230/LIPIcs.ESA.2022.9Licence: CC BY

SCI_Antoniadis_et alii_Computing Smallest Convex Intersecting PolygonsFinal published version, 915 KBLicence: CC BY

Cite this

Antoniadis, A., De Berg, M., Kisfaludi-Bak, S., & Skarlatos, A. (2022). Computing Smallest Convex Intersecting Polygons. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms, ESA 2022 Article 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 244). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.9

Antoniadis, Antonios ; De Berg, Mark ; Kisfaludi-Bak, Sándor et al. / Computing Smallest Convex Intersecting Polygons. 30th Annual European Symposium on Algorithms, ESA 2022. editor / Shiri Chechik ; Gonzalo Navarro ; Eva Rotenberg ; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{5fa759608d034400b0d19c4d41787f08,

title = "Computing Smallest Convex Intersecting Polygons",

abstract = "A polygon C is an intersecting polygon for a set O of objects in R2 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.",

keywords = "computational geometry, convex hull, imprecise points",

author = "Antonios Antoniadis and {De Berg}, Mark and S{\'a}ndor Kisfaludi-Bak and Antonis Skarlatos",

note = "Funding Information: Funding Mark de Berg is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Antonis Skarlatos: Part of the work was done during an internship at the Max Planck Institute for Informatics in Saarbr{\"u}cken, Germany. Publisher Copyright: {\textcopyright} 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; European Symposium on Algorithms, ESA ; Conference date: 05-09-2022 Through 09-09-2022",

year = "2022",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2022.9",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman",

booktitle = "30th Annual European Symposium on Algorithms, ESA 2022",

address = "Germany",

url = "https://algo2022.eu/esa/",

}

Antoniadis, A, De Berg, M, Kisfaludi-Bak, S & Skarlatos, A 2022, Computing Smallest Convex Intersecting Polygons. in S Chechik, G Navarro, E Rotenberg & G Herman (eds), 30th Annual European Symposium on Algorithms, ESA 2022., 9, Leibniz International Proceedings in Informatics, LIPIcs, vol. 244, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, European Symposium on Algorithms, Berlin and Potsdam, Germany, 05/09/2022. https://doi.org/10.4230/LIPIcs.ESA.2022.9

Computing Smallest Convex Intersecting Polygons. / Antoniadis, Antonios; De Berg, Mark; Kisfaludi-Bak, Sándor et al.
30th Annual European Symposium on Algorithms, ESA 2022. ed. / Shiri Chechik; Gonzalo Navarro; Eva Rotenberg; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 244).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Computing Smallest Convex Intersecting Polygons

AU - Antoniadis, Antonios

AU - De Berg, Mark

AU - Kisfaludi-Bak, Sándor

AU - Skarlatos, Antonis

N1 - Funding Information: Funding Mark de Berg is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Antonis Skarlatos: Part of the work was done during an internship at the Max Planck Institute for Informatics in Saarbrücken, Germany. Publisher Copyright: © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2022/9/1

Y1 - 2022/9/1

N2 - A polygon C is an intersecting polygon for a set O of objects in R2 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.

AB - A polygon C is an intersecting polygon for a set O of objects in R2 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.

KW - computational geometry

KW - convex hull

KW - imprecise points

UR - http://www.scopus.com/inward/record.url?scp=85137550638&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2022.9

DO - 10.4230/LIPIcs.ESA.2022.9

M3 - Conference article in proceedings

AN - SCOPUS:85137550638

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 30th Annual European Symposium on Algorithms, ESA 2022

A2 - Chechik, Shiri

A2 - Navarro, Gonzalo

A2 - Rotenberg, Eva

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - European Symposium on Algorithms

Y2 - 5 September 2022 through 9 September 2022

ER -

Computing Smallest Convex Intersecting Polygons

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this