Abstract
Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P1 and P2 such that the sum of the perimeters of CH(P1) and CH(P2) is minimized, where CH(Pi) denotes the convex hull of Pi. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n2) 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 2n) 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
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., Buchin, K., Mehr, M., & Mehrabi, A. D. (2020). Minimum perimeter-sum partitions in the plane. Discrete and Computational Geometry, 63(2), 483-505. https://doi.org/10.1007/s00454-019-00059-0