We consider the problem of maintaining, under insertions and deletions, the union of a set S of intervals on a line. We present a scheme that reports the ordered list of intervals in the union in Θ(k) time, while achieving O(log n) time in worst case for each insertion or deletion, where n is the number of intervals currently in S and k is the number of disjoint intervals in the union. The scheme uses Θ(n) space. This is an improvement upon a previous approach which uses O(log2 n) time for each insertion or deletion. Moreover, the insertion time is provably optimal for a certain class of structures. One of the applications of our scheme is an optimal contour algorithm for iso-oriented rectangles that is competitive, and in some cases better, when compared to known algorithms.
Bibliographical noteFunding Information:
*Research of both authors was supported in part by a grant-in-aid Graduate School of the University of Minnesota. The second author part by NSF Grant CCR-8808574.