20.500.12556/RUL-156134 Connectivity with uncertainty regions given as line segments For a set ${\mathcal Q}$ of points in the plane and a real number $\delta \ge 0$, let $\mathbb{G}_\delta({\mathcal Q})$ be the graph defined on ${\mathcal Q}$ by connecting each pair of points at distance at most $\delta$. We consider the connectivity of $\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}$ of $n-k$ points in the plane and a set ${\mathcal 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 {\mathcal S}$ and the corresponding graph $\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 ${\mathcal O}(f(k) n \log n)$ time, for a computable function $f(\cdot)$. This implies that the problem is FPT when parameterized by $k$. The best previous algorithm uses ${\mathcal O}((k!)^k k^{k+1}\cdot n^{2k})$ time and computes the solution up to fixed precision. computational geometry uncertainty geometric optimization fixed parameter tractability parametric search true false true Angleški jezik Ni določen Članek v reviji 2024-05-10 08:40:04 2024-05-10 08:40:05 2024-06-13 13:03:47 0000-00-00 00:00:00 2024 0 0 Str. 1512-1544 iss. 5 Vol. 86 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0178-4617 10.1007/s00453-023-01200-5 180364547 s00453-023-01200-5.pdf s00453-023-01200-5.pdf 1 91E7076F90671644948C34E586C81103 0851ef6ad3cad312bd32643a3401f4fc61d097bdda51da57c80988a91195eadc a28fbd79-0e98-11ef-99d3-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=183417 https://link.springer.com/article/10.1007/s00453-023-01200-5 0 7084af4b-0e98-11ef-99d3-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=183416 Fakulteta za matematiko in fiziko 0 0 0