Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments

This paper presents a dynamic data structure that can maintain a set S of pairwise-disjoint segments in the plane under insertions/deletions, and shows that a DFS tree (or forest) of G r ( S) can be computed in O ∗ ( n ) time.