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 (Corresponding author), Antonis Skarlatos

Research output: Contribution to journal › Article › Academic

273 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
Article number	2208.07567
Number of pages	28
Journal	arXiv
Volume	2022
DOIs	https://doi.org/10.48550/arXiv.2208.07567
Publication status	Published - 16 Aug 2022

Access to Document

10.48550/arXiv.2208.07567

pdfFinal published version, 1.16 MB

Cite this

@article{57c6fe1b699149b68d0951531890ddb5,

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. ",

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

year = "2022",

month = aug,

day = "16",

doi = "10.48550/arXiv.2208.07567",

language = "English",

volume = "2022",

journal = "arXiv",

issn = "2331-8422",

publisher = "Cornell University Library",

}

TY - JOUR

T1 - Computing Smallest Convex Intersecting Polygons

AU - Antoniadis, Antonios

AU - Berg, Mark de

AU - Kisfaludi-Bak, Sándor

AU - Skarlatos, Antonis

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.

U2 - 10.48550/arXiv.2208.07567

DO - 10.48550/arXiv.2208.07567

M3 - Article

SN - 2331-8422

VL - 2022

JO - arXiv

JF - arXiv

M1 - 2208.07567

ER -

Computing Smallest Convex Intersecting Polygons

Abstract

Access to Document

Fingerprint

Cite this