Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments

In this paper we study several proximity problems related to a set of pairwise-disjoint segments in R2. Let S be a set of n pairwise-disjoint segments in R2, and let r>0 be a parameter. We define the segment r-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(nlog2n)-time algorithm for computing a BFS tree of Gr(S). We apply it to obtain an O∗(n8/7)+O(nlog2nlogΔ)-time algorithm for the so-called reverse shortest path problem, in which given two segments s,t∈S and an integer k>0, we wish to compute the smallest value r∗ for which Gr∗(S) contains a path from s to t composed of at most k edges. (Here the O∗(·) notation hides polylogarithmic factors.) Here Δ=maxe≠e′∈Sdist(e,e′)/mine≠e′∈Sdist(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(log5n) amortized time. The amortized update time is also O(log5n). 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 Ω(n4/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(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(nlog4n) time. We also obtain an O(nlog3n)-time algorithm for constructing a minimum spanning tree of Gr(S). Finally, we present an O∗(n4/3)-time algorithm for computing a single-source shortest-path tree in Gr(S). This is the only result where we could not achieve a near-linear performance.

Duke Scholars

Author Pankaj K. Agarwal Computer Science