Computing Smallest Convex Intersecting Polygons

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorAntoniadis, Antoniosen_US
dc.contributor.authorDe Berg, Marken_US
dc.contributor.authorKisfaludi-Bak, Sándoren_US
dc.contributor.authorSkarlatos, Antonisen_US
dc.contributor.departmentUniversity of Twenteen_US
dc.contributor.departmentEindhoven University of Technologyen_US
dc.contributor.departmentProfessorship Kisfaludi-Bak Sándoren_US
dc.contributor.departmentUniversity of Salzburgen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorChechik, Shirien_US
dc.contributor.editorNavarro, Gonzaloen_US
dc.contributor.editorRotenberg, Evaen_US
dc.contributor.editorHerman, Grzegorzen_US
dc.date.accessioned2022-10-19T06:43:51Z
dc.date.available2022-10-19T06:43:51Z
dc.date.issued2022-09-01en_US
dc.descriptionFunding 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.
dc.description.abstractA 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.en
dc.description.versionPeer revieweden
dc.format.extent13
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationAntoniadis , A , De Berg , M , Kisfaludi-Bak , S & Skarlatos , A 2022 , Computing Smallest Convex Intersecting Polygons . in S Chechik , G Navarro , E Rotenberg & G Herman (eds) , 30th Annual European Symposium on Algorithms, ESA 2022 . , 9 , Leibniz International Proceedings in Informatics, LIPIcs , vol. 244 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , European Symposium on Algorithms , Berlin and Potsdam , Germany , 05/09/2022 . https://doi.org/10.4230/LIPIcs.ESA.2022.9en
dc.identifier.doi10.4230/LIPIcs.ESA.2022.9en_US
dc.identifier.isbn9783959772471
dc.identifier.issn1868-8969
dc.identifier.otherPURE UUID: 5fa75960-8d03-4400-b0d1-9c4d41787f08en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/5fa75960-8d03-4400-b0d1-9c4d41787f08en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85137550638&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/88521131/SCI_Antoniadis_et_alii_Computing_Smallest_Convex_Intersecting_Polygons.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/117219
dc.identifier.urnURN:NBN:fi:aalto-202210196007
dc.language.isoenen
dc.relation.ispartofEuropean Symposium on Algorithmsen
dc.relation.ispartofseries30th Annual European Symposium on Algorithms, ESA 2022en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics, LIPIcsen
dc.relation.ispartofseriesVolume 244en
dc.rightsopenAccessen
dc.subject.keywordcomputational geometryen_US
dc.subject.keywordconvex hullen_US
dc.subject.keywordimprecise pointsen_US
dc.titleComputing Smallest Convex Intersecting Polygonsen
dc.typeConference article in proceedingsfi
dc.type.versionpublishedVersion
Files
Collections
[article-cris] Perustieteiden korkeakoulu / SCI