TY - GEN

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

AU - Cheng, Siu Wing

AU - Janardan, Ravi

PY - 1990/1/1

Y1 - 1990/1/1

N2 - 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(logn) 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 0(n) space. This is an improvement upon a previous approach [7] which uses O(log2 n) time for each insertion or deletion. One of the applications of our scheme is an optimal contour algorithm for iso-oriented rectangles that is simpler and more practical than a previous optimal algorithm [4].

AB - 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(logn) 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 0(n) space. This is an improvement upon a previous approach [7] which uses O(log2 n) time for each insertion or deletion. One of the applications of our scheme is an optimal contour algorithm for iso-oriented rectangles that is simpler and more practical than a previous optimal algorithm [4].

UR - http://www.scopus.com/inward/record.url?scp=80052801334&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052801334&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:80052801334

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 74

EP - 83

BT - Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990

PB - Association for Computing Machinery

T2 - 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990

Y2 - 22 January 1990 through 24 January 1990

ER -