Minimum perimeter-sum partitions in the plane

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

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(n log4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ2 · log4 (1/ϵ)) time.

OriginalsprogEngelsk
Titel33rd International Symposium on Computational Geometry (SoCG 2017)
RedaktørerBoris Aronov, Matthew J. Katz
Antal sider15
ForlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato2017
Artikelnummer4
ISBN (Elektronisk)978-3-95977-038-5
DOI
StatusUdgivet - 2017
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
NavnLeibniz International Proceedings in Informatics
Vol/bind77
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 188450388