A Dynamic Data Structure Indexing Bounded Lines for Efficient  
Range Search

by Thuy Le

A dynamic data structure for efficient axis-aligned orthogonal range
search on a set of $n$ lines in a bounded plane is presented. The
algorithm requires $O(\log n + k)$ time in the worst case to find
all lines intersecting an axis aligned query rectangle $R$, for $k$
the number of lines in range. $O(n + \lambda)$ space is required for
the data structure used by the algorithm, where $\lambda$ is the
number of intersection points among the lines. Insertion of a new
rightmost line $\ell$ or deletion of a leftmost line $\ell$ requires
$O(n)$ time in the worst case. For a sparse arrangement of lines
(i.e., for $\lambda=O(n)$), insertion of a rightmost line $\ell$ or
deletion of a leftmost line $\ell$ requires $O(\sqrt{n})$ expected
time.

Joint work with Bradford G. Nickerson (UNB Faculty of Computer Science)