Computing Smallest Convex Intersecting Polygons

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

doi:10.48550/arXiv.2208.07567

Computing Smallest Convex Intersecting Polygons

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

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

3 Downloads (Pure)

Abstract

A polygon C is an intersecting polygon for a set O of objects in the plane 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
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.2208.07567
Publication status	Published - 16 Aug 2022

Keywords

cs.CG

Access to Document

10.48550/arXiv.2208.07567Licence: CC BY

2208.07567v1Final published version, 1.16 MBLicence: CC BY

1 Conference contribution
1 Article

Computing Smallest Convex Intersecting Polygons
Antoniadis, A., de Berg, M., Kisfaludi-Bak, S. & Skarlatos, A., 19 Feb 2025, In: Journal of computational geometry. 16, 1, p. 167-202 36 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
11 Downloads (Pure)
Computing Smallest Convex Intersecting Polygons
Antoniadis, A., de Berg, M., Kisfaludi-Bak, S. & Skarlatos, A., 2022, 30th Annual European Symposium on Algorithms (ESA 2022). Chechik, S., Navarro, G., Rotenberg, E. & Herman, G. (eds.). Dagstuhl, 13 p. 9. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 244).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
25 Downloads (Pure)

Cite this

@techreport{8b025d597a0c426b98bec0eb099c3a8e,

title = "Computing Smallest Convex Intersecting Polygons",

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

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

note = "Accepted to ESA 2022",

year = "2022",

month = aug,

day = "16",

doi = "10.48550/arXiv.2208.07567",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Computing Smallest Convex Intersecting Polygons

AU - Antoniadis, Antonios

AU - de Berg, Mark

AU - Kisfaludi-Bak, Sándor

AU - Skarlatos, Antonis

N1 - Accepted to ESA 2022

PY - 2022/8/16

Y1 - 2022/8/16

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

U2 - 10.48550/arXiv.2208.07567

DO - 10.48550/arXiv.2208.07567

M3 - Preprint

BT - Computing Smallest Convex Intersecting Polygons

PB - ArXiv.org

ER -

Computing Smallest Convex Intersecting Polygons

Abstract

Keywords

Access to Document

Fingerprint

Research output