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

Siu Wing Cheng, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)57-74
Number of pages18
JournalJournal of Algorithms
Issue number1
StatePublished - Mar 1991

Bibliographical note

Funding 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.


Dive into the research topics of 'Efficient maintenance of the union of intervals on a line, with applications'. Together they form a unique fingerprint.

Cite this