In this paper we study several proximity problems related to a set of pairwise-disjoint segments in \({\mathbb {R}}^2\) . Let S be a set of n pairwise-disjoint segments in \({\mathbb {R}}^2\) , and let \(r>0\) be a parameter. We define the segment r-proximity graph of S to be \(G_r(S):= (S,E)\) , where \(E = \{ (e_1,e_2) \mid \textrm{dist}(e_1,e_2) \le r\}\) and \(\textrm{dist}(e_1,e_2) = \min _{(p,q)\in e_1\times e_2} \Vert p-q\Vert \) is the Euclidean distance between \(e_1\) and \(e_2\) . We define the weight of an edge \((e_1,e_2) \in E\) to be \(\textrm{dist}(e_1,e_2)\) . We first present a simple grid-based \(O(n\log ^2 n)\) -time algorithm for computing a BFS tree of \(G_r(S)\) . We apply it to obtain an \(O^*(n^{8/7}) + O(n\log ^2n\log \Delta )\) -time algorithm for the so-called reverse shortest path problem, in which given two segments \(s, t \in S\) and an integer \(k>0\) , we wish to compute the smallest value \(r^*\) for which \(G_{r^*}(S)\) contains a path from s to t composed of at most k edges. (Here the \(O^*(\cdot )\) notation hides polylogarithmic factors.) Here \(\Delta = \max _{e\ne e' \in S} \textrm{dist}(e,e')/\min _{e\ne e' \in S} \textrm{dist}(e,e')\) is what we call the spread of S. Next, we present a dynamic data structure that can maintain a set S of pairwise-disjoint segments in the plane under insertions/deletions so that the segment of S closest to a query segment e, chosen from an unknown set Q of pairwise-disjoint segments, can be computed in \(O(\log ^5 n)\) amortized time. The amortized update time is also \(O(\log ^5 n)\) . We note that if the segments in \(S\cup Q\) are allowed to intersect then the known lower bounds on halfplane range searching suggest that a sequence of n updates and queries may take at least close to \(\Omega (n^{4/3})\) time in the worst case. One thus has to strongly rely on the non-intersecting property of S and Q to perform updates and queries in \(O(\textrm{polylog}(n))\) (amortized) time each. Using these results on nearest-neighbor (NN) searching for disjoint segments, we show that a DFS tree (or forest) of \(G_r(S)\) can be computed in \(O(n\log ^4n)\) time. We also obtain an \(O(n\log ^3n)\) -time algorithm for constructing a minimum spanning tree of \(G_r(S)\) . Finally, we present an \(O^*(n^{4/3})\) -time algorithm for computing a single-source shortest-path tree in \(G_r(S)\) . This is the only result where we could not achieve a near-linear performance.
