Minimum perimeter-sum partitions in the plane

M. Abrahamsen; M.T. de Berg; K.A. Buchin; M. Mehr; A.D. Mehrabi

doi:10.4230/LIPIcs.SoCG.2017.4

Minimum perimeter-sum partitions in the plane

M. Abrahamsen, M.T. de Berg, K.A. Buchin, M. Mehr, A.D. Mehrabi

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

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.

Original language	English
Title of host publication	33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia
Editors	Matthew J. Katz, Boris Aronov
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-15
Number of pages	15
ISBN (Electronic)	9783959770385
ISBN (Print)	978-3-95977-038-5
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2017.4
Publication status	Published - 1 Jun 2017
Event	33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia Duration: 4 Jul 2017 → 7 Jul 2017 Conference number: 33 http://socg2017.smp.uq.edu.au/socg.html http://socg2017.smp.uq.edu.au/index.html

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	77
ISSN (Print)	1868-8969

Conference

Conference	33rd International Symposium on Computational Geometry (SoCG 2017)
Abbreviated title	SoCG 2017
Country/Territory	Australia
City	Brisbane
Period	4/07/17 → 7/07/17
Other	The Computational Geometry Week (CG Week 2017) is the premier international forum for advances in computational geometry and its many applications. The next edition will take place in Brisbane, Australia, July 4-7, 2017. CG week combines a number of events, most notably the 33rd International Symposium on Computational Geometry (SoCG 2017), the associated multimedia exposition, workshops, and the Young Researchers Forum.
Internet address	http://socg2017.smp.uq.edu.au/socg.html http://socg2017.smp.uq.edu.au/index.html

Keywords

Clustering
Computational geometry
Convex hull
Minimum-perimeter partition

Access to Document

10.4230/LIPIcs.SoCG.2017.4

Cite this

Abrahamsen, M., de Berg, M. T., Buchin, K. A., Mehr, M., & Mehrabi, A. D. (2017). Minimum perimeter-sum partitions in the plane. In M. J. Katz, & B. Aronov (Eds.), 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia (pp. 1-15). Article 4 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 77). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.4

Abrahamsen, M. ; de Berg, M.T. ; Buchin, K.A. et al. / Minimum perimeter-sum partitions in the plane. 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia . editor / Matthew J. Katz ; Boris Aronov. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. pp. 1-15 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{608088c37a0047508a862db2e02c41b6,

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 P 1 and P 2 such that the sum of the perimeters of CH(P 1) and CH(P 2) 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 2) 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 4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ 2 · log 4 (1/ϵ)) time. ",

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

author = "M. Abrahamsen and {de Berg}, M.T. and K.A. Buchin and M. Mehr and A.D. Mehrabi",

year = "2017",

month = jun,

day = "1",

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

language = "English",

isbn = "978-3-95977-038-5",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

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

pages = "1--15",

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

booktitle = "33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia",

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

url = "http://socg2017.smp.uq.edu.au/socg.html, http://socg2017.smp.uq.edu.au/index.html",

}

Abrahamsen, M, de Berg, MT, Buchin, KA, Mehr, M & Mehrabi, AD 2017, Minimum perimeter-sum partitions in the plane. in MJ Katz & B Aronov (eds), 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia ., 4, Leibniz International Proceedings in Informatics, LIPIcs, vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 1-15, 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Queensland, Australia, 4/07/17. https://doi.org/10.4230/LIPIcs.SoCG.2017.4

Minimum perimeter-sum partitions in the plane. / Abrahamsen, M.; de Berg, M.T.; Buchin, K.A. et al.
33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia . ed. / Matthew J. Katz; Boris Aronov. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. p. 1-15 4 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 77).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Minimum perimeter-sum partitions in the plane

AU - Abrahamsen, M.

AU - de Berg, M.T.

AU - Buchin, K.A.

AU - Mehr, M.

AU - Mehrabi, A.D.

N1 - Conference code: 33

PY - 2017/6/1

Y1 - 2017/6/1

N2 - Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P 1 and P 2 such that the sum of the perimeters of CH(P 1) and CH(P 2) 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 2) 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 4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ 2 · log 4 (1/ϵ)) time.

AB - Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P 1 and P 2 such that the sum of the perimeters of CH(P 1) and CH(P 2) 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 2) 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 4 n) time and a (1 + ϵ)-approximation algorithm running in O(n + 1/ϵ 2 · log 4 (1/ϵ)) time.

KW - Clustering

KW - Computational geometry

KW - Convex hull

KW - Minimum-perimeter partition

UR - http://drops.dagstuhl.de/opus/volltexte/2017/7204/

UR - http://drops.dagstuhl.de/opus/volltexte/2017/7204/pdf/LIPIcs-SoCG-2017-4.pdf

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 - Conference contribution

SN - 978-3-95977-038-5

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 15

BT - 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia

A2 - Katz, Matthew J.

A2 - Aronov, Boris

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

CY - Dagstuhl

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

Y2 - 4 July 2017 through 7 July 2017

ER -

Abrahamsen M, de Berg MT, Buchin KA, Mehr M, Mehrabi AD. Minimum perimeter-sum partitions in the plane. In Katz MJ, Aronov B, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia . Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2017. p. 1-15. 4. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.SoCG.2017.4

Minimum perimeter-sum partitions in the plane

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this