A dynamic data structure for efficient bounded line range search

Description

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 l or deletion of a leftmost line l 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 l or deletion of a leftmost line l requires O (√n) expected time.