hide
Free keywords:
Computer Science, Computational Geometry, cs.CG
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.
