Minimum perimeter-sum partitions in the plane

Mikkel Abrahamsen; Mark de Berg; Kevin Buchin; Mehran Mehr; Ali D. Mehrabi

doi:10.1007/s00454-019-00059-0

Minimum perimeter-sum partitions in the plane

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

Algorithms, Geometry and Applications

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P₁ and P₂ such that the sum of the perimeters of CH(P1) and CH(P2) is minimized, where CH(Pi) denotes the convex hull of P_i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n²) 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 ²n) time and a (1 + ε) -approximation algorithm running in O(n+ 1 / ε²· log ²(1 / ε)) time.

Original language	English
Pages (from-to)	483-505
Number of pages	23
Journal	Discrete and Computational Geometry
Volume	63
Issue number	2
Early online date	1 Jan 2019
DOIs	https://doi.org/10.1007/s00454-019-00059-0
Publication status	Published - 1 Mar 2020

Keywords

Clustering
Computational geometry
Convex hull
Minimum-perimeter partition

Access to Document

10.1007/s00454-019-00059-0

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Minimum perimeter-sum partitions in the plane'. Together they form a unique fingerprint.

Cite this

@article{53de66d1aedb419ca5abaa125c377c47,

title = "Minimum perimeter-sum partitions in the plane",

abstract = "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.",

keywords = "Clustering, Computational geometry, Convex hull, Minimum-perimeter partition",

author = "Mikkel Abrahamsen and {de Berg}, Mark and Kevin Buchin and Mehran Mehr and Mehrabi, {Ali D.}",

year = "2020",

month = mar,

day = "1",

doi = "10.1007/s00454-019-00059-0",

language = "English",

volume = "63",

pages = "483--505",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Minimum perimeter-sum partitions in the plane

AU - Abrahamsen, Mikkel

AU - de Berg, Mark

AU - Buchin, Kevin

AU - Mehr, Mehran

AU - Mehrabi, Ali D.

PY - 2020/3/1

Y1 - 2020/3/1

N2 - 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.

AB - 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.

KW - Clustering

KW - Computational geometry

KW - Convex hull

KW - Minimum-perimeter partition

UR - http://www.scopus.com/inward/record.url?scp=85061204117&partnerID=8YFLogxK

U2 - 10.1007/s00454-019-00059-0

DO - 10.1007/s00454-019-00059-0

M3 - Article

AN - SCOPUS:85061204117

VL - 63

SP - 483

EP - 505

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 2

ER -