Minimum Perimeter-Sum Partitions in the Plane

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 $\text{CH}(P_1)$ and $\text{CH}(P_2)$ is minimized, where $\text{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(n{\log }^{2}n)$ time and a $(1+\epsilon )$-approximation algorithm running in $O(n+1/{\epsilon }^2\cdot {\log }^2(1/\epsilon ))$ time.

arXiv commentThis version is similar to one published in Discrete & Computational Geometry