Minimum perimeter-sum partitions in the plane
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Discrete & Computational Geometry |
Vol/bind | 63 |
Sider (fra-til) | 483–505 |
ISSN | 0179-5376 |
DOI | |
Status | Udgivet - 2020 |
Begivenhed | 33rd International Symposium on Computational Geometry - Brisbane, Australien Varighed: 4 jul. 2017 → 7 jul. 2017 Konferencens nummer: 33 |
Konference
Konference | 33rd International Symposium on Computational Geometry |
---|---|
Nummer | 33 |
Land | Australien |
By | Brisbane |
Periode | 04/07/2017 → 07/07/2017 |
Links
- http://arxiv.org/pdf/1703.05549
Indsendt manuskript
ID: 212990217