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
B, such that all
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
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?