Minimum perimeter-sum partitions in the plane

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

doi:10.4230/LIPIcs.SoCG.2017.4

Minimum perimeter-sum partitions in the plane

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

Datalogisk Institut

3 Citationer (Scopus)

39 Downloads (Pure)

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(P₁) and CH(P₂) 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²) 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(n log⁴ n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ² · log⁴ (1/ϵ)) time.

Originalsprog	Engelsk
Titel	33rd International Symposium on Computational Geometry (SoCG 2017)
Redaktører	Boris Aronov, Matthew J. Katz
Antal sider	15
Forlag	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato	2017
Artikelnummer	4
ISBN (Elektronisk)	978-3-95977-038-5
DOI	https://doi.org/10.4230/LIPIcs.SoCG.2017.4
Status	Udgivet - 2017
Begivenhed	33rd International Symposium on Computational Geometry - Brisbane, Australien Varighed: 4 jul. 2017 → 7 jul. 2017 Konferencens nummer: 33

Konference

Konference	33rd International Symposium on Computational Geometry
Nummer	33
Land/Område	Australien
By	Brisbane
Periode	04/07/2017 → 07/07/2017

Navn	Leibniz International Proceedings in Informatics
Vol/bind	77
ISSN	1868-8969

Adgang til dokumentet

10.4230/LIPIcs.SoCG.2017.4Licens: CC BY

Abrahamsen_2017_Minimum_perimeter-sumForlagets udgivne version, 652 KBLicens: CC BY

Andre filer og links

Link to publication in Scopus

Citationsformater

Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M., & Mehrabi, A. D. (2017). Minimum perimeter-sum partitions in the plane. I B. Aronov, & M. J. Katz (red.), 33rd International Symposium on Computational Geometry (SoCG 2017) [4] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics Bind 77 https://doi.org/10.4230/LIPIcs.SoCG.2017.4

Minimum perimeter-sum partitions in the plane. / Abrahamsen, Mikkel; de Berg, Mark; Buchin, Kevin et al.

33rd International Symposium on Computational Geometry (SoCG 2017). red. / Boris Aronov; Matthew J. Katz. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. 4 (Leibniz International Proceedings in Informatics, Bind 77).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Abrahamsen, M, de Berg, M, Buchin, K, Mehr, M & Mehrabi, AD 2017, Minimum perimeter-sum partitions in the plane. i B Aronov & MJ Katz (red), 33rd International Symposium on Computational Geometry (SoCG 2017)., 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, bind 77, 33rd International Symposium on Computational Geometry, Brisbane, Queensland, Australien, 04/07/2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.4

@inproceedings{4778c64dcbad49589d9bc8b656378a46,

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(n log4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ2 · log4 (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 = "2017",

doi = "10.4230/LIPIcs.SoCG.2017.4",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Boris Aronov and Katz, {Matthew J.}",

booktitle = "33rd International Symposium on Computational Geometry (SoCG 2017)",

note = "33rd International Symposium on Computational Geometry ; Conference date: 04-07-2017 Through 07-07-2017",

}

TY - GEN

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.

N1 - Conference code: 33

PY - 2017

Y1 - 2017

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

KW - Clustering

KW - Computational geometry

KW - Convex hull

KW - Minimum-perimeter partition

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

U2 - 10.4230/LIPIcs.SoCG.2017.4

DO - 10.4230/LIPIcs.SoCG.2017.4

M3 - Article in proceedings

AN - SCOPUS:85029923349

T3 - Leibniz International Proceedings in Informatics

BT - 33rd International Symposium on Computational Geometry (SoCG 2017)

A2 - Aronov, Boris

A2 - Katz, Matthew J.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 33rd International Symposium on Computational Geometry

Y2 - 4 July 2017 through 7 July 2017

ER -

Minimum perimeter-sum partitions in the plane

Abstract

Konference

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater