Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments

In this paper we study a few proximity problems related to a set of pairwise-disjoint segments in R². Let S be a set of n pairwise-disjoint segments in R², and let r > 0 be a parameter. We define the segment proximity graph of S to be Gr(S):= (S,E), where E = {(e1,e2) | dist(e1,e2) ≤ r} and dist(e1,e2) = min(p,q)∈e1×e2 ∥p − q∥ is the Euclidean distance between e1 and e2. We define the weight of an edge (e1,e2) ∈ E to be dist(e1,e2). We first present a simple grid-based O(nlog² n)-time algorithm for computing a BFS tree of Gr(S). We apply it to obtain an O^∗(n^6/5)+O(nlog² nlog ∆)-time algorithm for the so-called reverse shortest path problem, in which we want to find the smallest value r^∗ for which Gr∗(S) contains a path of some specified length between two designated start and target segments (where the O^∗(·) notation hides polylogarithmic factors). Here ∆ = maxe≠e′∈S dist(e,e^′)/mine≠e′∈S dist(e,e^′) is 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, for a query segment e from an unknown set Q of pairwise-disjoint segments, such that e does not intersect any segment in (the current version of) S, the segment of S closest to e can be computed in O(log⁵ n) amortized time. The amortized update time is also O(log⁵ n). We note that if the segments in S∪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 Ω(n^4/3) time. One thus has to strongly rely on the non-intersecting property of S and Q to perform updates and queries in O(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 Gr(S) can be computed in O^∗(n) time. We also obtain an O^∗(n)-time algorithm for constructing a minimum spanning tree of Gr(S). Finally, we present an O^∗(n^4/3)-time algorithm for computing a single-source shortest-path tree in Gr(S). This is the only result that does not exploit the disjointness of the input segments.

Duke Scholars

Author Pankaj K. Agarwal Computer Science