20.500.12556/DiRROS-18913 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 Neznano 2024-05-13 10:15:17 2024-05-13 10:15:17 2024-05-14 03:35:33 0000-00-00 00:00:00 2024 0 0 str. 1512-1544 iss. 5 Vol. 86 May 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2024-05-01 519.17 0178-4617 10.1007/s00453-023-01200-5 180364547 s00453-023-01200-5-2.pdf s00453-023-01200-5-2.pdf 1 17304811F1157DDF1FCA980BD1E379BD ea9758e77dcff1b9d8045ca8dfc2eb681e6b4cb7bce3f1a73f746e22e8b89fef 3433ccec-1101-11ef-9c9e-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25907 https://link.springer.com/article/10.1007/s00453-023-01200-5 0 3cc53d58-1101-11ef-9c9e-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25908 Inštitut za matematiko, fiziko in mehaniko 0 0 0