Efficient way to count number of intersections of line segments

Question

On my computer science course's exam I was given the following task:

You are given $n$ segments that lies on the same line: $i$-th segment starts at coordinate $from_i$ and ends at $to_i$. Your task is for each segment count number of other segments that intersects it.

EXAMPLE INPUT:
5
7 8
8 9
0 3
2 7
10 15

EXAMPLE OUTPUT:
2 1 1 2 0

I've implemented the naive algorithm:

def count_intersections(i):
    counter = 0
    for j in range(len(data)):
        if i != j:
            if data[i][0] <= data[j][0]:
                left = data[i]
                right = data[j]
            else:
                left = data[j]
                right = data[i]
            
            if right[0] <= left[1] <= right[1]:
                counter += 1
            elif left[0] <= right[0] <= left[1]:
                counter += 1
            
    return counter

n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int, input().split())))

for i in range(n):
    print(count_intersections(i), end = ' ')

As you can see, I just iterate through eacher other segment and increment counter if it intersect the given one. Time complexity of my solution is $O(n^2)$. And because of this I got Tme Limit Error.

Do you know more efficient solution? Maybe some extraordinal Data Structure?

Answer 1

Let's first assume there is no common boundaries between all segments.

Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the index of the segment, sorted by $pos$. Sorting is achieved in $O(n \log(n)).$

Keep two counters, $open$, the number of opened segments and $close$, the number of closed segments. Both are initially at 0.

$E[i]$ will be an array of the segment $i$ state, where 0 means not opened yet, 1 otherwise.

$A[i]$ will be the $n$-element array to output, which are 0s initially.

Then loop through the list,

for tuple (pos, i),
    if E[i] == 0, then A[i] = close, open += 1, E[i] = 1
    else A[i] = open-A[i]-1, close += 1

The "-1" stands for a segment not counting himself.

This achieves $O(n)$, then still driven by the sorting $O(n \log(n))$.

Now, how to treat common boundaries ? In your exemple, I understand that segments are closed and for example [2, 7] does intersect [7, 8]. A simple way to do it (clearly not the most efficient but still $O(n)$), is to loop 3 times on the tuples at the same position:

• first, you only count the opening segments in $open$
• then, you only update $E[i]$ and $A[i]$ for both opening and closing segments
• finally, you only count the closing segments in $close$ (that now have $E[i] = 2$)

Answer 2

Edit: By mistake I thought we were working in 2 dimensions, this answer is for the 2d case. (I don't know why plshelp mentioned order statistics tree in his/her deleted answer because I didn't understood it but maybe he/she misunderstood like me.)

We can use a sweep line algorithm. We think of each active segments as a 1d moving point while we are sweeping the plane.

We store the list of active segments in an order statistics tree (as said by plshelp in a now deleted answer) and we use a priority queue of "events". We store in the "events" each start/end of a segment and also the (dynamically added and removed) intersections.

We continuously update for each active segment the time of intersection with the next segment in the list of active segments and store it in the priority queue. When treating an event:

1. If this is a start or an end, we add or remove the corresponding active segments.
2. If this is an intersection, we increment the number of intersections and swap the two corresponding segments in the list.

We also update the new times of intersections (removing or adding at most a low bounded number of items in the priority queue).

Notice that when inserting a new segment, the comparison function must use the current time, but the elements already in the list are necessarily sorted even if the comparison function has changed. This algorithm is in $O((n+k)\log(n))$ where $n$ is the number of segments and $k$ is the number of intersections, since the priority queue cannot store more than $3n$ events.