aalto1 untyped-item.component.html
Computing smallest convex intersecting polygons
Loading...
Access rights
openAccess
CC BY
CC BY
Creative Commons license
Except where otherwised noted, this item's license is described as openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
36
Series
Journal of Computational Geometry, Volume 16, issue 1, pp. 167-202
Abstract
A polygon C is an intersecting polygon for a set (Present Formula) of objects in R2 if C intersects each object in (Present Formula), 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 (Present Formula) of objects. We present an FPTAS for both problems for the case where (Present Formula) 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 minim umperimeter intersecting polygon for the case where (Present Formula) 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.
Description
Publisher Copyright: © 2025 Carleton University. All rights reserved.
Keywords
Other note
Citation
Antoniadis, A, de Berg, M, Kisfaludi-Bak, S & Skarlatos, A 2025, 'Computing smallest convex intersecting polygons', Journal of Computational Geometry, vol. 16, no. 1, pp. 167-202. https://doi.org/10.20382/jocg.v16i1a6