Dynamic length of union of segments (1d Klee's measure problem)

Question

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of their union. There is a simple $O(n \log n)$ solution involving sorting endpoints of all intervals and then iterating over them while keeping track of some counters.

Now let's look at a dynamic variant of this problem: we are receiving $n$ segments one after another and the task is to find the length of the current union of segments after each new segment arrives. It seems like a natural generalization, however, I cannot find much information about this version of the problem. I wonder if it is still possible to solve this problem in $O(n \log n)$ time in an offline setting, i.e. when we are given all segments beforehand and can preprocess them in some way before giving an answer for each segment.

I feel like a modification of a segment tree might be useful here. In every node we need to keep track of both the total sum of lengths of segments (or their parts) corresponding to this node and the length of their union. However, I cannot figure out how to implement this modification without performance of one update degrading to linear time in some cases. Maybe using a segment tree is not the right approach and a better way exists.

Update:

What if we make the problem even more difficult by also allowing to delete previously added segments? Can it still be solved offline in $O(n \log n)$ time where $n$ is the total number of add/delete segment queries?

Answer 1

The online version can be solved in $O(n\log n)$ amortised time, possibly using the technique you already came up with. The key is to maintain just the nonoverlapping intervals that result from merging intervals wherever necessary.

Maintain an ordered list of the endpoints of segments in a binary search tree, with each endpoint represented by a pair $(x, type)$, where $type$ is either $start$ or $stop$. New intervals will be merged with these so that the segments in the tree are nonoverlapping at all times. When a new segment $[a, b]$ arrives, add $b-a$ to the total length, and search the tree to find all contained endpoints. For each such endpoint:

• If it is $(x, start)$, add $x$ to the total length.
• If it is $(x, stop)$, subtract $x$ from the total length.
• Delete it.

If the leftmost such endpoint is a $start$, or if there are no endpoints, then insert $a$ as a $start$ endpoint; otherwise, if there was at least one endpoint (the leftmost of which must be a $stop$), add $a$ to the total length. If the rightmost such endpoint is a $stop$, or if there are no endpoints, then add $b$ as a $stop$ endpoint; otherwise, if there was at least one endpoint (the rightmost of which must be a $start$), subtract $b$ from the total length.

To understand why the time complexity is not quadratic even though an individual operation can take $O(n)$ time, notice that a preexisting interval never needs to be merged with other intervals more than twice (once to its left, once to its right), so we can conservatively pay the cost of these potential merges at the time we create the interval; since merging amounts to removing an endpoint, the cost of performing a merge is constant, so the overall time complexity doesn't change. Basically, any time we have to merge a bunch of intervals, we remove the possibility of having to merge them in the future.

Answer 2

In the case when all additions and deletions are known beforehand, there is an algorithm of $O(n\log n)$ time-complexity. The basic idea is to decompose each interval into $O(\log n)$ "key intervals" and keep track the number of times key intervals are covered in a designated binary tree.

Collect and sort all endpoints of all intervals that have been added or deleted. We get $a_0, a_1, \cdots, a_{n-1}$, where $n$ is the total number of distinct endpoints. (If $n-1$ is not a power of 2, add some extra points.

Construct a tree each node of which has an interval as its key. The keys of the leaves are all intervals of the form $[a_i, a_{i+1}]$. The parent of the leaves with key $[a_{2i}, a_{2i+1}]$ and $[a_{2i+1}, a_{2i+2}]$ is the node whose key is $[a_{2i},a_{2i+2}]$. The parent of the nodes with key $[a_{2i}, a_{2i+2}]$ and $[a_{2i+2}, a_{2i+4}]$ is the node with key $[a_{2i},a_{2i+4}]$. And so on. Each node of the tree has a key of the form $[a_i,a_j]=[a_{2^mk}, a_{2^m(k+1)}]$. Its left child is the node with key $[a_i, a_{(i+j)/2}]$ and its right child is the node with key $[a_{(i+j)/2}, a_j]$. We will call all those intervals "key intervals". Any interval whose endpoints are among $a_0, a_1, \cdots, a_n$ decomposes into $O (\log (n))$ key intervals naturally.

Each node of the tree will store a couple of other quantities. First, it will store the real_length, $a_j-a_i$ where $[a_i,a_j]$ is its key interval. Second, it will store covering_intervals_count, the number of intervals in the current set of intervals containing its key interval. Thirdly, it will store covered_length, which is the the length of the union of all current intervals covered by its key interval. The current covered_length of the root node is the current length of the union of all current intervals.

How to maintain the values ​​of these three quantities when intervals are added and removed?

• The value of read_length does not change during these operations. They will be set when the tree is initialized. Note that for parent node $s$, $s$.real_length = left_child($s$).real_length + гight_child($s$).real_length.
• The value of covering_intervals_count increases by one iff an added interval covers the corresponding key interval. Similarly, it decreases by one if a deleted interval covers the corresponding key interval.
• The value of covered_length is equal to real_length if the current value of covering_intervals_count is positive. So, real_length does not need to be touched as long as covering_intervals_count is positive. If it is reduced to zero, then we have to compute, recursively as further as necessary, s.covered_length = left_child(s).covered_length + right_child(s).covered_length.

Further detail in Russian are available in WPS2010.pdf, a file in this folder on Google Drive. You can find Problem D, Длина объединения (Join Length) and more explanation, starting from page 109.