Minimum perimeter-sum partitions in the plane

Research output: Contribution to journalJournal articlepeer-review

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.
Original languageEnglish
JournalDiscrete & Computational Geometry
Volume63
Pages (from-to)483–505
ISSN0179-5376
DOIs
Publication statusPublished - 2020
Event33rd International Symposium on Computational Geometry - Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017
Conference number: 33

Conference

Conference33rd International Symposium on Computational Geometry
Number33
CountryAustralia
CityBrisbane
Period04/07/201707/07/2017

    Research areas

  • Clustering, Computational geometry, Convex hull, Minimum-perimeter partition

Links

ID: 212990217