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 contribution › Academic › peer-review

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
Pages	9:1-9:13
Number of pages	13
ISBN (Electronic)	9783959772471
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2022.9
Publication status	Published - 1 Sept 2022

Bibliographical note

DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Keywords

computational geometry
convex hull
imprecise points

Access to Document

10.4230/LIPIcs.ESA.2022.9

Cite this

@inproceedings{6e804818be2c489b97911e4f9c759bbb,

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 Berg, {Mark de} and S{\'a}ndor Kisfaludi-Bak and Antonis Skarlatos",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2022",

month = sep,

day = "1",

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

language = "English",

pages = "9:1--9:13",

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

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

}

Computing Smallest Convex Intersecting Polygons. / Antoniadis, Antonios; Berg, Mark de; Kisfaludi-Bak, Sándor et al.
30th Annual European Symposium on Algorithms, ESA 2022. ed. / Shiri Chechik; Gonzalo Navarro; Eva Rotenberg; Grzegorz Herman. 2022. p. 9:1-9:13.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Computing Smallest Convex Intersecting Polygons.

AU - Antoniadis, Antonios

AU - Berg, Mark de

AU - Kisfaludi-Bak, Sándor

AU - Skarlatos, Antonis

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

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

SP - 9:1-9:13

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

A2 - Chechik, Shiri

A2 - Navarro, Gonzalo

A2 - Rotenberg, Eva

A2 - Herman, Grzegorz

ER -

Computing Smallest Convex Intersecting Polygons.

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this