Minimum perimeter-sum partitions in the plane

Research output: Contribution to journalJournal articleResearchpeer-review

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P 1 P1 and P 2 P2 such that the sum of the perimeters of CH(P 1 ) CH(P1) and CH(P 2 ) CH(P2) is minimized, where CH(P i ) CH(Pi) denotes the convex hull of P i Pi. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n 2 ) 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(nlog 2 n) O(nlog2⁡n) time and a (1+ε) (1+ε)-approximation algorithm running in O(n+1/ε 2 ⋅log 2 (1/ε)) O(n+1/ε2⋅log2⁡(1/ε)) time.
Original languageEnglish
JournalDiscrete & Computational Geometry
Publication statusE-pub ahead of print - 2019
Event33rd International Symposium on Computational Geometry - Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017
Conference number: 33


Conference33rd International Symposium on Computational Geometry

    Research areas

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

ID: 212990217