Minimum perimeter-sum partitions in the plane

Mikkel Abrahamsen (Corresponding author), Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

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

Originele taal-2Engels
Pagina's (van-tot)483-505
Aantal pagina's23
TijdschriftDiscrete and Computational Geometry
Volume63
Nummer van het tijdschrift2
Vroegere onlinedatum1 jan 2019
DOI's
StatusGepubliceerd - 1 mrt 2020

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

  • Citeer dit