Minimum perimeter-sum partitions in the plane

TY - JOUR

T1 - Minimum perimeter-sum partitions in the plane

AU - Abrahamsen, Mikkel

AU - de Berg, Mark

AU - Buchin, Kevin

AU - Mehr, Mehran

AU - Mehrabi, Ali D.

N1 - Conference code: 33

PY - 2020/3/1

Y1 - 2020/3/1

N2 - 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(nlog 2n) time and a (1 + ε) -approximation algorithm running in O(n+ 1 / ε2· log 2(1 / ε)) time.

AB - 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(nlog 2n) time and a (1 + ε) -approximation algorithm running in O(n+ 1 / ε2· log 2(1 / ε)) time.

KW - Clustering

KW - Computational geometry

KW - Convex hull

KW - Minimum-perimeter partition

U2 - 10.1007/s00454-019-00059-0

DO - 10.1007/s00454-019-00059-0

M3 - Journal article

SN - 0179-5376

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

T2 - 33rd International Symposium on Computational Geometry

Y2 - 4 July 2017 through 7 July 2017

ER -