Minimum perimeter-sum partitions in the plane

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfæ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(nlog2⁡n) time and a (1+ε) (1+ε)-approximation algorithm running in O(n+1/ε 2 ⋅log 2 (1/ε)) O(n+1/ε2⋅log2⁡(1/ε)) time.
OriginalsprogEngelsk
TidsskriftDiscrete & Computational Geometry
Vol/bind63
Sider (fra-til)483–505
ISSN0179-5376
DOI
StatusUdgivet - 2020
Begivenhed33rd International Symposium on Computational Geometry - Brisbane, Australien
Varighed: 4 jul. 20177 jul. 2017
Konferencens nummer: 33

Konference

Konference33rd International Symposium on Computational Geometry
Nummer33
LandAustralien
ByBrisbane
Periode04/07/201707/07/2017

Links

ID: 212990217