Minimum perimeter-sum partitions in the plane
Research output: Contribution to journal › Journal article › peer-review
Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P 1 P1 and P 2 P2 such that the sum of the perimeters of CH(P 1 ) CH(P1) and CH(P 2 ) CH(P2) is minimized, where CH(P i ) CH(Pi) denotes the convex hull of P i Pi. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n 2 ) 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 2 n) O(nlog2n) time and a (1+ε) (1+ε)-approximation algorithm running in O(n+1/ε 2 ⋅log 2 (1/ε)) O(n+1/ε2⋅log2(1/ε)) time.
Original language | English |
---|---|
Journal | Discrete & Computational Geometry |
Volume | 63 |
Pages (from-to) | 483–505 |
ISSN | 0179-5376 |
DOIs | |
Publication status | Published - 2020 |
Event | 33rd International Symposium on Computational Geometry - Brisbane, Australia Duration: 4 Jul 2017 → 7 Jul 2017 Conference number: 33 |
Conference
Conference | 33rd International Symposium on Computational Geometry |
---|---|
Number | 33 |
Country | Australia |
City | Brisbane |
Period | 04/07/2017 → 07/07/2017 |
- Clustering, Computational geometry, Convex hull, Minimum-perimeter partition
Research areas
Links
- http://arxiv.org/pdf/1703.05549
Submitted manuscript
ID: 212990217