Standard
Minimum perimeter-sum partitions in the plane. / Abrahamsen, Mikkel; de Berg, Mark; Buchin, Kevin; Mehr, Mehran; Mehrabi, Ali D.
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 › fagfællebedømt
Harvard
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
APA
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
Vancouver
Abrahamsen M, de Berg M, Buchin K, Mehr M, Mehrabi AD.
Minimum perimeter-sum partitions in the plane. I Aronov B, Katz MJ, red., 33rd International Symposium on Computational Geometry (SoCG 2017). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2017. 4. (Leibniz International Proceedings in Informatics, Bind 77).
https://doi.org/10.4230/LIPIcs.SoCG.2017.4
Author
Abrahamsen, Mikkel ; de Berg, Mark ; Buchin, Kevin ; Mehr, Mehran ; Mehrabi, Ali D. / Minimum perimeter-sum partitions in the plane. 33rd International Symposium on Computational Geometry (SoCG 2017). red. / Boris Aronov ; Matthew J. Katz. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. (Leibniz International Proceedings in Informatics, Bind 77).
Bibtex
@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 = "null ; Conference date: 04-07-2017 Through 07-07-2017",
}
RIS
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
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
Y2 - 4 July 2017 through 7 July 2017
ER -
