Minimum perimeter-sum partitions in the plane

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P1 and P2 such that the sum of the perimeters of CH(P1) and CH(P2) is minimized, where CH(Pi) denotes the convex hull of Pi. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ2 · log4 (1/ϵ)) time.

Original languageEnglish
Title of host publication33rd International Symposium on Computational Geometry (SoCG 2017)
EditorsBoris Aronov, Matthew J. Katz
Number of pages15
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2017
Article number4
ISBN (Electronic)978-3-95977-038-5
DOIs
Publication statusPublished - 2017
Event33rd International Symposium on Computational Geometry - Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017
Conference number: 33

Conference

Conference33rd International Symposium on Computational Geometry
Nummer33
LandAustralia
ByBrisbane
Periode04/07/201707/07/2017
SeriesLeibniz International Proceedings in Informatics
Volume77
ISSN1868-8969

    Research areas

  • Clustering, Computational geometry, Convex hull, Minimum-perimeter partition

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 188450388