Minimum perimeter-sum partitions in the plane

M. Abrahamsen, M.T. de Berg, K.A. Buchin, M. Mehr, A.D. Mehrabi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

50 Downloads (Pure)

Samenvatting

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P 1 and P 2 such that the sum of the perimeters of CH(P 1 ) and CH(P 2 ) is minimized, where CH(P i ) denotes the convex hull of P i . The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n 2 ) 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 4 n) time and a (1+ε) -approximation algorithm running in O(n+1/ε 2 ⋅log 4 (1/ε)) time.
Originele taal-2Engels
Artikelnummer1703.05549
Aantal pagina's19
TijdschriftarXiv
Nummer van het tijdschrift1703.05549
StatusGepubliceerd - 2017

Vingerafdruk Duik in de onderzoeksthema's van 'Minimum perimeter-sum partitions in the plane'. Samen vormen ze een unieke vingerafdruk.

Citeer dit