Minimum perimeter-sum partitions in the plane

M. Abrahamsen, M.T. de Berg, K.A. Buchin, M. Mehr, A.D. Mehrabi

Research output: Contribution to journalArticleAcademic

92 Downloads (Pure)


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(nlog 4 n) time and a (1+ε) -approximation algorithm running in O(n+1/ε 2 ⋅log 4 (1/ε)) time.
Original languageEnglish
Article number1703.05549
Number of pages19
Issue number1703.05549
Publication statusPublished - 2017


Dive into the research topics of 'Minimum perimeter-sum partitions in the plane'. Together they form a unique fingerprint.

Cite this