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

Siu Wing Cheng, Ravi Janardan

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

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
Volume12
Issue number1
DOIs
StatePublished - Mar 1991

Fingerprint 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