Connectivity with Uncertainty Regions Given as Line Segments

For a set \({\mathcal {Q}}\) $\mathcal{Q}$ of points in the plane and a real number \(\delta \ge 0\) $\delta \ge 0$ , let \({\mathbb {G}}_\delta ({\mathcal {Q}})\) ${\mathbb{G}}_{\delta }(\mathcal{Q})$ be the graph defined on \({\mathcal {Q}}\) $\mathcal{Q}$ by connecting each pair of points at distance at most \(\delta \) $\delta$ .We consider the connectivity of \({\mathbb {G}}_\delta ({\mathcal {Q}})\) ${\mathbb{G}}_{\delta }(\mathcal{Q})$ 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 \({\mathcal {P}}\) $\mathcal{P}$ of \(n-k\) $n-k$ points in the plane and a set \({\mathcal {S}}\) $\mathcal{S}$ of k line segments in the plane, find the minimum \(\delta \ge 0\) $\delta \ge 0$ with the property that we can select one point \(p_s\in s\) $p_s\in s$ for each segment \(s\in {\mathcal {S}}\) $s\in \mathcal{S}$ and the corresponding graph \({\mathbb {G}}_\delta ( {\mathcal {P}}\cup \{ p_s\mid s\in {\mathcal {S}}\})\) ${\mathbb{G}}_{\delta }(\mathcal{P}\cup \{p_s\mid s\in \mathcal{S}\})$ is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in \({{\,\mathrm{{\mathcal {O}}}\,}}(f(k) n \log n)\) $\mathcal{O}(f(k)nlogn)$ time, for a computable function \(f(\cdot )\) $f(·)$ . This implies that the problem is FPT when parameterized by k. The best previous algorithm uses \({{\,\mathrm{{\mathcal {O}}}\,}}((k!)^k k^{k+1}\cdot n^{2k})\) $\mathcal{O}({(k!)}^k{k}^{k+1}·n^{2k})$ time and computes the solution up to fixed precision.