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.
| Original language | English |
|---|---|
| Number of pages | 23 |
| Journal | Discrete and Computational Geometry |
| DOIs | |
| Publication status | E-pub ahead of print - 1 Jan 2019 |
Fingerprint
Keywords
- Clustering
- Computational geometry
- Convex hull
- Minimum-perimeter partition
Cite this
}
Minimum perimeter-sum partitions in the plane. / Abrahamsen, Mikkel (Corresponding author); de Berg, Mark; Buchin, Kevin; Mehr, Mehran; Mehrabi, Ali D.
In: Discrete and Computational Geometry, 01.01.2019.Research output: Contribution to journal › Article › Academic › peer-review
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 - 2019/1/1
Y1 - 2019/1/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
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
SN - 0179-5376
ER -