## 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(n log
^{4} n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ
^{2} · log
^{4} (1/ϵ)) time.

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

Title of host publication | 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia |

Editors | Matthew J. Katz, Boris Aronov |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 1-15 |

Number of pages | 15 |

ISBN (Electronic) | 9783959770385 |

ISBN (Print) | 978-3-95977-038-5 |

DOIs | |

Publication status | Published - 1 Jun 2017 |

Event | 33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia Duration: 4 Jul 2017 → 7 Jul 2017 Conference number: 33 http://socg2017.smp.uq.edu.au/socg.html http://socg2017.smp.uq.edu.au/index.html |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 77 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 33rd International Symposium on Computational Geometry (SoCG 2017) |
---|---|

Abbreviated title | SoCG 2017 |

Country/Territory | Australia |

City | Brisbane |

Period | 4/07/17 → 7/07/17 |

Other | The Computational Geometry Week (CG Week 2017) is the premier international forum for advances in computational geometry and its many applications. The next edition will take place in Brisbane, Australia, July 4-7, 2017. CG week combines a number of events, most notably the 33rd International Symposium on Computational Geometry (SoCG 2017), the associated multimedia exposition, workshops, and the Young Researchers Forum. |

Internet address |

## Keywords

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