### 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 language | English |
---|---|

Article number | 1703.05549 |

Number of pages | 19 |

Journal | arXiv |

Issue number | 1703.05549 |

Publication status | Published - 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