## 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(P1) and CH(P2) is minimized, where CH(Pi) 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 ^{2}n) time and a (1 + ε) -approximation algorithm running in O(n+ 1 / ε^{2}· log ^{2}(1 / ε)) time.

Original language | English |
---|---|

Pages (from-to) | 483-505 |

Number of pages | 23 |

Journal | Discrete and Computational Geometry |

Volume | 63 |

Issue number | 2 |

Early online date | 1 Jan 2019 |

DOIs | |

Publication status | Published - 1 Mar 2020 |

## Keywords

- Clustering
- Computational geometry
- Convex hull
- Minimum-perimeter partition