4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the detailed answer, it was very helpful! However, I've updated the question after realizing that one more natural generalization of the problem is to also allow deleting previously added segments. I wonder if it can still be solved in O(nlogn) time? I've tried to modify your approach to also solve this new version of the problem, however, I can't figure out how to do it because we are loosing a lot of information when merging overlapping segments. $\endgroup$ – David Dec 7 '19 at 22:29
  • $\begingroup$ You're welcome :) Allowing deletions makes it much harder, and I don't see a way to extend my approach to handle them (as you say, because too much information is lost). I don't see a way to accomplish this in $O(n\log n)$ time ("blinking" a long interval on and off, intermixed with random other insertions and deletions, seems particularly hard to hande quickly), but I also don't see a way to rule out the possibility (e.g. via a known lower bound). $\endgroup$ – j_random_hacker Dec 8 '19 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.