Fast fencing

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedings – Annual report year: 2018Researchpeer-review

Standard

Fast fencing. / Abrahamsen, Mikkel; Adamaszek, Anna; Bringmann, Karl; Cohen-Addad, Vincent; Mehr, Mehran; Rotenberg, Eva; Roytman, Alan; Thorup, Mikkel.

Proceedings of 50th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2018. p. 1319-1332 (Proceedings of the Annual Acm Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedings – Annual report year: 2018Researchpeer-review

Harvard

Abrahamsen, M, Adamaszek, A, Bringmann, K, Cohen-Addad, V, Mehr, M, Rotenberg, E, Roytman, A & Thorup, M 2018, Fast fencing. in Proceedings of 50th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, Proceedings of the Annual Acm Symposium on Theory of Computing, pp. 1319-1332, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, United States, 25/06/2018. https://doi.org/10.1145/3188745.3188878

APA

Abrahamsen, M., Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., ... Thorup, M. (2018). Fast fencing. In Proceedings of 50th Annual ACM Symposium on Theory of Computing (pp. 1319-1332). Association for Computing Machinery. Proceedings of the Annual Acm Symposium on Theory of Computing https://doi.org/10.1145/3188745.3188878

CBE

Abrahamsen M, Adamaszek A, Bringmann K, Cohen-Addad V, Mehr M, Rotenberg E, Roytman A, Thorup M. 2018. Fast fencing. In Proceedings of 50th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 1319-1332. (Proceedings of the Annual Acm Symposium on Theory of Computing). https://doi.org/10.1145/3188745.3188878

MLA

Abrahamsen, Mikkel et al. "Fast fencing". Proceedings of 50th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. (Proceedings of the Annual Acm Symposium on Theory of Computing). 2018, 1319-1332. https://doi.org/10.1145/3188745.3188878

Vancouver

Abrahamsen M, Adamaszek A, Bringmann K, Cohen-Addad V, Mehr M, Rotenberg E et al. Fast fencing. In Proceedings of 50th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. 2018. p. 1319-1332. (Proceedings of the Annual Acm Symposium on Theory of Computing). https://doi.org/10.1145/3188745.3188878

Author

Abrahamsen, Mikkel ; Adamaszek, Anna ; Bringmann, Karl ; Cohen-Addad, Vincent ; Mehr, Mehran ; Rotenberg, Eva ; Roytman, Alan ; Thorup, Mikkel. / Fast fencing. Proceedings of 50th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2018. pp. 1319-1332 (Proceedings of the Annual Acm Symposium on Theory of Computing).

Bibtex

@inproceedings{3bdbcb558bf540dcb5be462afd6ce115,
title = "Fast fencing",
abstract = "We consider very natural “fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves, we present an algorithm that is polynomial in both n and k. For the variant with unit cost per curve, or unit disks, we present a near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in nO(k) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k. Our polynomial time algorithm refutes this unless P equals NP.",
keywords = "Geometric clustering, Minimum perimeter sum",
author = "Mikkel Abrahamsen and Anna Adamaszek and Karl Bringmann and Vincent Cohen-Addad and Mehran Mehr and Eva Rotenberg and Alan Roytman and Mikkel Thorup",
year = "2018",
doi = "10.1145/3188745.3188878",
language = "English",
isbn = "9781450355599",
pages = "1319--1332",
booktitle = "Proceedings of 50th Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
address = "United States",

}

RIS

TY - GEN

T1 - Fast fencing

AU - Abrahamsen, Mikkel

AU - Adamaszek, Anna

AU - Bringmann, Karl

AU - Cohen-Addad, Vincent

AU - Mehr, Mehran

AU - Rotenberg, Eva

AU - Roytman, Alan

AU - Thorup, Mikkel

PY - 2018

Y1 - 2018

N2 - We consider very natural “fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves, we present an algorithm that is polynomial in both n and k. For the variant with unit cost per curve, or unit disks, we present a near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in nO(k) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k. Our polynomial time algorithm refutes this unless P equals NP.

AB - We consider very natural “fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves, we present an algorithm that is polynomial in both n and k. For the variant with unit cost per curve, or unit disks, we present a near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in nO(k) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k. Our polynomial time algorithm refutes this unless P equals NP.

KW - Geometric clustering

KW - Minimum perimeter sum

U2 - 10.1145/3188745.3188878

DO - 10.1145/3188745.3188878

M3 - Article in proceedings

SN - 9781450355599

SP - 1319

EP - 1332

BT - Proceedings of 50th Annual ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

ER -