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

49 Downloads (Pure)

Abstract

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
JournalarXiv
Issue number1703.05549
Publication statusPublished - 2017

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

  • Cite this

    Abrahamsen, M., de Berg, M. T., Buchin, K. A., Mehr, M., & Mehrabi, A. D. (2017). Minimum perimeter-sum partitions in the plane. arXiv, (1703.05549), [1703.05549]. https://arxiv.org/abs/1703.05549