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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

7 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	30th Annual European Symposium on Algorithms, ESA 2022
Toimittajat	Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
Kustantaja	Schloss Dagstuhl-Leibniz-Zentrum für Informatik
Sivumäärä	13
ISBN (elektroninen)	9783959772471
DOI - pysyväislinkit	https://doi.org/10.4230/LIPIcs.ESA.2022.9
Tila	Julkaistu - 1 syysk. 2022
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	European Symposium on Algorithms - Berlin and Potsdam, Saksa Kesto: 5 syysk. 2022 → 9 syysk. 2022 https://algo2022.eu/esa/

Julkaisusarja

Nimi	Leibniz International Proceedings in Informatics, LIPIcs
Vuosikerta	244
ISSN (painettu)	1868-8969

Conference

Conference	European Symposium on Algorithms
Lyhennettä	ESA
Maa/Alue	Saksa
Kaupunki	Berlin and Potsdam
Ajanjakso	05/09/2022 → 09/09/2022
www-osoite	https://algo2022.eu/esa/

Pääsy asiakirjaan

10.4230/LIPIcs.ESA.2022.9Lisenssi: CC BY

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

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

Siteeraa tätä

Antoniadis, A., De Berg, M., Kisfaludi-Bak, S., & Skarlatos, A. (2022). Computing Smallest Convex Intersecting Polygons. teoksessa S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Toimittajat), 30th Annual European Symposium on Algorithms, ESA 2022 [9] (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 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. Toimittaja / 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. julkaisussa S Chechik, G Navarro, E Rotenberg & G Herman (toim), 30th Annual European Symposium on Algorithms, ESA 2022., 9, Leibniz International Proceedings in Informatics, LIPIcs, Vuosikerta 244, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, European Symposium on Algorithms, Berlin and Potsdam, Saksa, 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. toim. / Shiri Chechik; Gonzalo Navarro; Eva Rotenberg; Grzegorz Herman. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 244).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

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 contribution

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 -

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

Computing Smallest Convex Intersecting Polygons

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä