Fast fencing

Mikkel Abrahamsen; Anna Adamaszek; Karl Bringmann; Vincent Cohen-Addad; Mehran Mehr; Eva Rotenberg; Alan Roytman; Mikkel Thorup

doi:10.1145/3188745.3188878

Fast fencing

Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup

Department of Computer Science

1 Citation (Scopus)

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 n^O(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.

Original language	English
Title of host publication	STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Publication date	2018
Pages	564-573
ISBN (Electronic)	9781450355599
DOIs	https://doi.org/10.1145/3188745.3188878
Publication status	Published - 2018
Event	50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018

Conference

Conference	50th Annual ACM Symposium on Theory of Computing, STOC 2018
Country/Territory	United States
City	Los Angeles
Period	25/06/2018 → 29/06/2018
Sponsor	ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)

Keywords

Geometric clustering
Minimum perimeter sum

Access to Document

10.1145/3188745.3188878

3188745.3188878Final published version, 822 KB

https://dl.acm.org/doi/pdf/10.1145/3188745.3188878

Cite this

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

@inproceedings{c6184f105897446c8cc8236a030d513e,

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",

pages = "564--573",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

note = "50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

}

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

UR - http://www.scopus.com/inward/record.url?scp=85049877511&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188878

DO - 10.1145/3188745.3188878

M3 - Article in proceedings

AN - SCOPUS:85049877511

SP - 564

EP - 573

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -

Fast fencing

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this