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(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].
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990 |
| Publisher | Association for Computing Machinery |
| Pages | 74-83 |
| Number of pages | 10 |
| ISBN (Electronic) | 0898712513 |
| State | Published - Jan 1 1990 |
| Event | 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990 - San Francisco, United States Duration: Jan 22 1990 → Jan 24 1990 |
Publication series
| Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|
Other
| Other | 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990 |
|---|---|
| Country/Territory | United States |
| City | San Francisco |
| Period | 1/22/90 → 1/24/90 |
Bibliographical note
Funding Information:Given a set S = {srts2, . ..) of possibly overlap- ping intervals on a line, we consider the problem of maintaining efficiently, under insertions and deletions in S, the union of the intervals in S. The union of the intervals is a set of non-overlapping intervals. The problem of maintaining the union has been considered previously in [7], under the general framework of order-decomposabIe set problems. In [7], a scheme is presented for reporting the intervals in the union (in left-to-right order) in O(h) time, while realizing O(log* n) time in worst case for each insertion or deletion, where n is the nurn-ber of intervals currently in S and k is the number of intervals in the union. The space used is 0(n). In this paper, we improve upon the result in [7] by reducing the time for insertions and deletions to O(log n) in worst case while still being able to *Department of Computer Science, University 55455 +This research wss SUPPO~ h Pa by a gra&in-aid of research from the Grad-uate School of the University of Minnesota. The second author was also supported in part by NSF grad CCR8808574.