Connectivity with Uncertainty Regions Given as Line Segments

Abstract

For a set $Q$ of points in the plane and a real number $\delta \ge 0$, let $G_{\delta }\left(Q\right)$ be the graph defined on $Q$ by connecting each pair of points at distance at most $\delta$.We consider the connectivity of $G_{\delta }\left(Q\right)$ in the best scenario when the location of a few of the points is uncertain, but we know for each uncertain point a line segment that contains it. More precisely, we consider the following optimization problem: given a set $P$ of $n-k$ points in the plane and a set $S$ of k line segments in the plane, find the minimum $\delta \ge 0$ with the property that we can select one point $p_s\in s$ for each segment $s\in S$ and the corresponding graph $G_{\delta }(P\cup \{p_s\mid s\in S\})$ is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in $O\left(f\right(k)nlogn)$ time, for a computable function $f(·)$. This implies that the problem is FPT when parameterized by k. The best previous algorithm uses $O({(k!)}^k{k}^{k+1}·n^{2k})$ time and computes the solution up to fixed precision.

Keywords: Computational geometry; Fixed parameter tractability; Geometric optimization; Parametric search; Uncertainty.