Minimum perimeter-sum partitions in the plane

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.