Fast fencing

DOI10.1145/3188745.3188878MaRDI QIDQ5230320zbMATH OpenOpenAlexFDO

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

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.00101

zbMATH Keywords

geometric clusteringminimum perimeter sum

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Geometric Knapsack problems
• scientific article; zbMATH DE number 4066651
• scientific article; zbMATH DE number 177546
• Geometric multicut: shortest fences for separating groups of objects in the plane
• Minimum-perimeter enclosures

Cited in

(8)

• scientific article; zbMATH DE number 177546 (Why is no real title available?)
• scientific article; zbMATH DE number 7561502 (Why is no real title available?)
• Exact and heuristic solutions for the prize‐collecting geometric enclosure problem
• Isoperimetric enclosures
• Approximation algorithms for the geometric firefighter and budget fence problems
• Minimum perimeter-sum partitions in the plane
• Clustering with few disks to minimize the sum of radii
• Geometric multicut: shortest fences for separating groups of objects in the plane

This page was built for publication: Fast fencing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230320)