Connectivity with uncertainty regions given as line segments

Cabello, Sergio (author), Gajser, David (author)

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.

• Language: English
• Keywords: computational geometry, uncertainty, geometric optimization, fixed parameter tractability, parametric search
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2024
• Number of pages: Str. 1512-1544
• Numbering: Vol. 86, iss. 5
• PID: 20.500.12556/RUL-156134
• UDC: 519.17
• ISSN on article: 0178-4617
• DOI: 10.1007/s00453-023-01200-5
• COBISS.SI-ID: 180364547
• Publication date in RUL: 10.05.2024

Record is a part of a journal

• Title: Algorithmica
• Shortened title: Algorithmica
• Publisher: Springer Nature
• ISSN: 0178-4617
• COBISS.SI-ID: 24917760

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.