Connectivity with uncertainty regions given as line segments
share
For a set Q of points in the plane and a real number δ≥ 0, let 𝔾_δ(Q) be the graph defined on Q by connecting each pair of points at distance at most δ. We consider the connectivity of 𝔾_δ(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 P of n-k points in the plane and a set 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∈ S and the corresponding graph 𝔾_δ ( P∪{ p_s| s∈ S}) is connected. It is known that the problem is NP-hard. We provide an algorithm to compute exactly an optimal solution in O(f(k) n log n) time, for a computable function f(·). This implies that the problem is FPT when parameterized by k. The best previous algorithm is using O((k!)^k k^k+1· n^2k) time and computes the solution up to fixed precision.
READ FULL TEXT