Conference paper
Fast fencing
University of Copenhagen1
Max Planck Institute for Informatics2
Sorbonne Université3
Eindhoven University of Technology4
Department of Applied Mathematics and Computer Science, Technical University of Denmark5
Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark6
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.
Language: | English |
---|---|
Publisher: | Association for Computing Machinery |
Year: | 2018 |
Pages: | 1319-1332 |
Proceedings: | 50<sup>th</sup> Annual ACM SIGACT Symposium on Theory of Computing |
Journal subtitle: | Proceedings of the 50th Annual Acm Sigact Symposium on Theory of Computing |
ISBN: | 1450355595 and 9781450355599 |
Types: | Conference paper |
DOI: | 10.1145/3188745.3188878 |
ORCIDs: | Rotenberg, Eva , 0000-0003-2734-4690 , 0000-0003-3291-0124 and 0000-0001-5237-1709 |