Efficient maintenance of the union of intervals on a line, with applications

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(log² 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.