Connectivity with uncertainty regions given as line segmentsCabello, Sergio (Avtor) Gajser, David (Avtor) computational geometryuncertaintygeometric optimizationfixed parameter tractabilityparametric searchFor a set $\mathcal{Q}$ of points in the plane and a real number $δ$ ≥ 0, let $\mathbb{G}_δ(\mathcal{Q})$ be the graph defined on $\mathcal{Q}$ by connecting each pair of points at distance at most $δ$. We consider the connectivity of $\mathbb{G}_δ(\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}$ of $n$ – $k$ points in the plane and a set $\mathcal{S}$ of $k$ line segments in the plane, find the minimum $δ$ ≥ 0 with the property that we can select one point $p_s$ ∈ $s$ for each segment $s$ ∈ $\mathcal{S}$ and the corresponding graph $\mathbb{G}_δ(\mathcal{P} ∪ \{p_s$ | $s ∈ \mathcal{S}\})$ is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in $\mathcal{O}( f (k)n$ ${\rm log}$ $n)$ time, for a computable function $f$ (·). This implies that the problem is FPT when parameterized by $k$. The best previous algorithm uses $\mathcal{O}((k!)^kk^{k+1} · n^{2k})$ time and computes the solution up to fixed precision.20242024-05-12 06:55:41Znanstveno delo88567UDK: 519.17COBISS_ID: 180364547DOI: 10.1007/s00453-023-01200-5ISSN pri članku: 0178-4617sl