2026-07-17T12:56:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7204 2024-03-06T10:39:56Z ddc:004 open_access

Minimum Perimeter-Sum Partitions in the Plane Abrahamsen, Mikkel de Berg, Mark Buchin, Kevin Mehr, Mehran Mehrabi, Ali D. Computational geometry clustering minimum-perimeter partition convex hull Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P_1 and P_2 such that the sum of the perimeters of CH(P_1) and CH(P_2) is minimized, where CH(P_i) denotes the convex hull of P_i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n^2) 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 log^4 n) time and a (1+e)-approximation algorithm running in O(n + 1/e^2 log^4(1/e)) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen and Mark de Berg and Kevin Buchin and Mehran Mehr and Ali D. Mehrabi 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.4 urn:nbn:de:0030-drops-72048 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode