Dynamic Orthogonal Segment Intersection Search and Its Applications(GRAPH THEORY AND APPLICATIONS)
Hiroshi Imai, Takao Asano · Kyoto University Research Information Repository (Kyoto University) · 1984
This paper develops data structures for maintaining a set of orthogonal segments, where a segment in the plane is called orthogonal if it is horizontal or vertical.By combining the data structures with graph algorithms for depth-first search, matchings, etc., or with algorithms in computational geometry, we obtain algorithms, with better time complexities, for problems on orthogonal segments, which arise in various fields such as VLSI design, computer graphics and database system.