Connectivity with uncertainty regions given as line segments

Cabello, Sergio (avtor), Gajser, David (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: computational geometry, uncertainty, geometric optimization, fixed parameter tractability, parametric search
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2024
• Št. strani: Str. 1512-1544
• Številčenje: Vol. 86, iss. 5
• PID: 20.500.12556/RUL-156134
• UDK: 519.17
• ISSN pri članku: 0178-4617
• DOI: 10.1007/s00453-023-01200-5
• COBISS.SI-ID: 180364547
• Datum objave v RUL: 10.05.2024

Gradivo je del revije

• Naslov: Algorithmica
• Skrajšan naslov: Algorithmica
• Založnik: Springer Nature
• ISSN: 0178-4617
• COBISS.SI-ID: 24917760

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.