How can we find the number of pairs of intersecting ranges on a circular number line?

Question

I recently thought of and managed to solve this algorithmic problem:

On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers A and B, such that all A and B are unique. Each pair of integers then represents the starting and ending points of a range on the number line. How many distinct pairs of ranges intersect?

^^ In this example, 4 distinct pairs of segments intersect.

Obviously, there is a O(N^2) brute-force solution: just test all possible pairs in O(1) time each. However, I also thought of a O(NlogN) sweep-line algorithm: treat every A as a "segment start event" and every B as a "segment end event". Then, keep a variable curr_in_range (originally 0) that stores the current number of segments that we currently see, and then iterate through the events in sorted order of their positions on the number line. Every time we add another segment, add curr_in_range to the answer (because this new segment will intersect with every other segment that we can see) and increment it as well. Every time we remove a segment, decrement curr_in_range. In the end, this gets us the correct answer.

Happy with this algorithm, I decided to tackle a slightly modified version of this problem: What if the number line is circular? As in, it has a specified length L such that the number line contains numbers in the range [0, L)? In this case, each range would still be specified by two distinct integers A and B, but let's just say the range is always counterclockwise starting from A and ending at B. Could we still find the number of pairs of sectors that intersect in less than O(N^2) time in this scenario?

Here's my thought process on this problem:

We should be able to use a very similar algorithm to the one described above. Completely copying it wouldn't work, though, because the sectors can have B < A when it crosses over 0. My idea was to initially have curr_in_range equal to the number of sectors that cross over 0 (instead of just it at 0 like we did in the above algorithm). Then, we could treat every sector as a "sector start event" and a "sector end event", and do the same process that we did.

However, after extensive analysis, I found why this approach doesn't work. This approach won't work because it overcounts some of the intersections, as sometimes two sectors can intersect in 2 places. This is where I'm stuck.

^^ Our sweep-line algorithm will count 2 distinct pairs that intersect, when there is actually only 1.

But besides this overcounting, I found that this current algorithm isn't doing a single other thing wrong. I coded a O(N^2) brute-force algorithm and tabulated all the distinct pairs that it found, and also tabulated the distinct pairs found for the current algorithm. For every randomly-generated test case, these two tables were the same. In other words, our current algorithm is correctly detecting every intersection there is to be detected, but it just happens to overcount some of them.

So, sorry for a really long post, but my final question is:

Can someone come up with an algorithm that solves this problem? Is my thought process close to a solution or completely off?

Answer 1

Summary

Interesting question.

Please check this program in Java that runs in $O(n\log n)$ time, where $n$ is the number of given ranges. The program uses sweep-line technique, once for counting intersecting pairs of ranges, and once for counting containing pairs of ranges together with Fenwick tree. Explanations follow.

Reduce to the hard case

Here are the notations and assumptions for the ease of explanation.

• All numbers and variables are integers.
• The numbered circle of cardinality $L\ge2$ is the set of number $0, 1, \cdots, L-1$, where $L$ is considered to wrap around to $0$.
• A range $[s,e]$ with respect to $L$, where $0\le s\le e\lt L$, means
  • a non-wrapping range (a.k.a. an ordinary range) if $s\le e$, i.e., numbers $s, s+1,\cdots, e-1, e$;
  • a wrapping range otherwise, i.e,. numbers $s, s+1, \cdots, L-1, 0, 1, \cdots, e-1, e$.

Note every range contains at least one number. The non-wrapping range $[0, L-1]$ contains all the numbers. So does every wrapping range like $[s,s-1]$.

Suppose there are $n$ ranges. The question is how to compute the number of all unordered pairs of two intersecting ranges efficiently.

There are three cases for an unordered pair of two ranges.

• Both ranges are wrapping.
  This is the easiest case since two wrapping ranges always intersect at $0$.

• Both ranges are non-wrapping.
  This is the classical case. The total number of such intersecting pairs can be computed by the sweep-line (or, as I would call it, the sweep-point or sweep-event) algorithm, which runs in $O(n)$ time, as described in the question.

• One range is non-wrapping and the other is wrapping.
  This is the new and hard case. One way to understand why this case may not be easy is j_random_hacker's illustration. How can we deal with this case?

Transform to the containing pairs of non-wrapping pairs

Denote the non-wrapping ranges and the wrapping ranges in the given ranges by $\mathcal N$ and $\mathcal W$, respectively. Instead of counting the intersecting pairs between $\mathcal N$ and $\mathcal W$, we will use complementary counting, i.e., we will count the non-intersecting pairs between $\mathcal N$ and $\mathcal W$.

Given any range $r$, let $\overline r$ be the numbers among $0, 1, \cdots, L-1$ that are not in $r$, i.e., the complement of $r$ with respect to $\mathcal C$. Note that two ranges do NOT intersect iff the complement of either one contains the other.

Let $\overline{\mathcal W} = \{\overline r\mid r\in\mathcal W\}$. Then the number of non-intersecting pairs between $\mathcal N$ and $\mathcal W$ is the number of containing pairs between $\mathcal N$ and $\overline{\mathcal W}$. Here a containing pair means, naturally, two sets $a$ and $c$ such that $c$ contains $a$. The number we wanted, i.e., the number of all intersecting pairs of ranges between $\mathcal N$ and $\mathcal W$ is $|\mathcal N|\cdot|\mathcal W|$ minus that number of containing pairs.

More formally, we have $$\#\{(a, b) \mid a\in{\mathcal N}, b\in{\mathcal W}, a\cap b\not=\emptyset\} = \#{\mathcal N}\cdot\#{\mathcal W} - \#\{(a, c) \mid a\in{\mathcal N}, c\in\overline{\mathcal W}, a\subseteq c\}. $$

Here is a simple observation, the complement of a wrapping range is a non-wrapping range, except when the wrapping range is like $[s,s-1]$, whose complement is empty. Containing all numbers, a wrapping range like that intersects with every other range. It is easy to count all intersecting pairs that involve a wrapping range like that.

Let us assume there is no such wrapping range; if necessary, we can replace such a range with non-wrapping range $[0, L-1]$. The problem is reduced to counting the number of containing pairs between two sets of non-wrapping ranges.

An algorithm that counts the number of containing pairs

Here is an algorithm that counts the number of containing pairs between two given sets of non-wrapping ranges, $\mathcal N$ and $\overline{\mathcal W}$. It is, basically, sweep-line technique together with Fenwick tree.

1. Let containingPairCount = 0.
2. Initialize a Fenwick tree (a.k.a. binary indexed tree) ft for an (implicit) interested array of length $L$, with all values 0 initially. The e-th element of the interested array will be the number of all ranges in $\overline{\mathcal W}$ so far that end at e.
3. Sort all ranges that are in either $\overline{\mathcal W}$ or $\mathcal N$ by the starting points, breaking ties by putting ranges in $\overline{\mathcal W}$ before ranges in $\mathcal N$. Breaking the remaining ties arbitrarily.
4. One by one process the sorted ranges. Let the current range be [s,e].
   • If it comes from $\overline{\mathcal W}$, updates the Fenwick tree as if the e-th element of the interested array is increased by 1. This operation registers the current range as a candidate containing range that has started and will end at e.
   • If it comes from $\mathcal N$, add the sum of elements of indexes no smaller than e in the interested array to containingPairCount, by containingPairCount += st.getSum(e, L-1).
5. Return containingPairCount.

Proof of the algorithm: st.getSum(e, L-1) is the number of all ranges in $\overline{\mathcal W}$ that contain the current non-wrapping range, since, thanks to the careful setup, we have processed all ranges in $\overline{\mathcal W}$ that start at or before the start of the current range, and only those ranges that end at or after the end of the current edge are counted. $\quad\checkmark$

The sorting of all ranges at step 3 takes $O(n\log n)$ time. At step 4, each range is processed with $O(\log n)$ time, thanks to the power of Fenwick tree. So the running time of this algorithm is $O(n\log n) + O(n \log n) = O(n\log n)$.

Complexity analysis

The running time for other parts of the entire algorithm is $O(n\log n)$, which is spent mostly on counting the intersecting non-wrapping pairs. So, the running time of the entire algorithm is $O(n\log n) + O(n \log n) = O(n\log n)$.

---

_{The sections "Reduce to the hard case" and "transform to the containing pairs of non-wrapping pairs" follow D.W's answer roughly.}

Answer 2

This is solvable in $O(n \log n)$ time, too, by considering the complement of the intervals that wrap around and using a suitable data structure.

There are two types of intervals that can appear on a cycle:

• Intervals that do not wrap around: e.g., $[0.3,0.5]$ does not wrap around. In general, this includes all intervals of the form $[a,b]$ with $0\le a \le b \le 1$.

• Intervals that wrap around: e.g., $[0.8,0.1]$ wraps around; it is equivalent to $[0.8,1.1]$ or $[0.8,1] \cup [0,0.1]$. In general, this includes all intervals of the form $[b,a]$ with $0\le a < b \le 1$; each such interval is equivalent to $[b,1] \cup [0,a]$.

Let $A$ denote the set of intervals that do not wrap around, and $B$ the set of intervals that do wrap around. Also, let $\overline{B}$ denote the complements of the intervals in $B$, i.e., $\overline{B} = \{\overline{b} \mid b \in B\}$. For instance, the interval $[0.8,0.1]$ wraps around; its complement is $(0.1,0.8)$, which does not wrap around. It is easier to think about intervals that do not wrap around, and this decomposition will help us to deal only with intervals that do not wrap around.

Now, we will separately count the number of overlaps between (1) an interval in $A$ and an interval in $A$; (2) an interval in $A$ and an interval in $B$; (3) an interval in $B$ and an interval in $A$; and (4) an interval in $B$ and an interval in $B$. (1) can be counted with your sweepline algorithm, as we don't need to deal with wraparound. (4) can also be counted in the same way, as two intervals overlap iff their complements overlap. I will show below how to count (2); case (3) will then follow by symmetry. This covers all the cases, so it suffices to count up these four cases and sum them up.

Note that intervals $a \in A, b\in B$ overlap iff $a$ is not a subset of $\overline{b}$. So, it suffices to count the number of pairs $a \in A, \overline{b}\in \overline{B}$ where $a$ is a subset of $\overline{b}$; then you can subtract that from $|A| \cdot |B|$.

To do that, you can use the data structure in Data structure for interval subset queries. Store all the intervals $\overline{B}$ in the data structure. Then, for each $a \in A$, count the number of intervals in $\overline{B}$ that $a$ is a subset of. This can be done in $O(\log n)$ time per query interval $a$, for a total time of $O(n \log n)$.

Therefore, you can count each of the four cases in $O(n \log n)$ time, and thus compute the overall sum in $O(n \log n)$ time as well. I think. I encourage you to check my reasoning to make sure I haven't made any mistakes.

Answer 3

Not a solution, just an illustration of what I see as the core difficulty:

The instance on the left has 3 intersections, the one on the right only 2, but there is no way to distinguish the instances just by counting numbers of "begin segment" and "end segment" events within a given interval. (Inside the gap left by the red interval, the event sequence is "begin", "end" in both cases.)

This implies that a sweep-line approach needs to track more information about each active segment -- probably their identities, which suggests to me that no fast algorithm will be possible, though that's just a feeling.