Minimum perimeter-sum partitions in the plane

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Minimum perimeter-sum partitions in the plane. / Abrahamsen, Mikkel; de Berg, Mark; Buchin, Kevin; Mehr, Mehran; Mehrabi, Ali D.

I: Discrete & Computational Geometry, Bind 63, 2020, s. 483–505.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Abrahamsen, M, de Berg, M, Buchin, K, Mehr, M & Mehrabi, AD 2020, 'Minimum perimeter-sum partitions in the plane', Discrete & Computational Geometry, bind 63, s. 483–505. https://doi.org/10.1007/s00454-019-00059-0

APA

Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M., & Mehrabi, A. D. (2020). Minimum perimeter-sum partitions in the plane. Discrete & Computational Geometry, 63, 483–505. https://doi.org/10.1007/s00454-019-00059-0

Vancouver

Abrahamsen M, de Berg M, Buchin K, Mehr M, Mehrabi AD. Minimum perimeter-sum partitions in the plane. Discrete & Computational Geometry. 2020;63:483–505. https://doi.org/10.1007/s00454-019-00059-0

Author

Abrahamsen, Mikkel ; de Berg, Mark ; Buchin, Kevin ; Mehr, Mehran ; Mehrabi, Ali D. / Minimum perimeter-sum partitions in the plane. I: Discrete & Computational Geometry. 2020 ; Bind 63. s. 483–505.

Bibtex

@article{f7043159c74d4034818be8b29ad7f102,
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 P1 and P 2 P2 such that the sum of the perimeters of CH(P 1 ) CH(P1) and CH(P 2 ) CH(P2) is minimized, where CH(P i ) CH(Pi) denotes the convex hull of P i Pi. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n 2 ) 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 2 n) O(nlog2⁡n) time and a (1+ε) (1+ε)-approximation algorithm running in O(n+1/ε 2 ⋅log 2 (1/ε)) O(n+1/ε2⋅log2⁡(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",
doi = "10.1007/s00454-019-00059-0",
language = "English",
volume = "63",
pages = "483–505",
journal = "Discrete & Computational Geometry",
issn = "0179-5376",
publisher = "Springer",
note = "null ; Conference date: 04-07-2017 Through 07-07-2017",

}

RIS

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.

N1 - Conference code: 33

PY - 2020

Y1 - 2020

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

KW - Clustering

KW - Computational geometry

KW - Convex hull

KW - Minimum-perimeter partition

U2 - 10.1007/s00454-019-00059-0

DO - 10.1007/s00454-019-00059-0

M3 - Journal article

VL - 63

SP - 483

EP - 505

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

SN - 0179-5376

Y2 - 4 July 2017 through 7 July 2017

ER -

ID: 212990217