Fast fencing

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 -