## Fast fencing

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings – Annual report year: 2018 › Research › peer-review

### Standard

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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings – Annual report year: 2018 › Research › peer-review

### Harvard

*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

*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

### MLA

*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

### Author

### Bibtex

}

### 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 -