20.500.12556/DKUM-88567 Connectivity with uncertainty regions given as line segments For 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. computational geometry uncertainty geometric optimization fixed parameter tractability parametric search računalniška geometrija negotovost geometrijska optimizacija sledljivost s fiksnimi parametri parametrično iskanje true false true Angleški jezik Slovenski jezik Znanstveno delo 2024-05-12 06:55:41 2025-10-21 14:23:35 2025-10-22 03:08:45 0000-00-00 00:00:00 2024 0 0 str. 1512-1544 št. 5 Letn. 6 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2023-03-17 2023-12-11 2024-01-09 519.17 180364547 10.1007/s00453-023-01200-5 0178-4617 RAZ_Cabello_Sergio_2024.pdf RAZ_Cabello_Sergio_2024.pdf 1 DB4D9F8EFC927B763D18C6AFE0557AC9 531e3b504b5c8cdbc0cac6b016728b4b88d61e72e213a90124a9e6b17378822a aff65b59-ae79-11f0-a9c6-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=200071 http://dx.doi.org/10.1007/s00453-023-01200-5 1 e3745c3f-101b-11ef-bee8-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=179234 Fakulteta za naravoslovje in matematiko 0 0 0