Fast dynamic intersection searching in a set of isothetic line segments

Abstract

We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log2 n) space requirements and O(log3 n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(log N + t) query time, O(n log2 N) space and O(log2 N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique. © 1985.