Is it possible to efficiently count the number of line segments that overlap one point P on a number line?

Question

Is it possible to efficiently count the number of line segments that overlap one point P on a number line?

All line segments are located on the same number line (its world is 1-D , not the world 3-D ).

Each line segment has an initial coordinate X1 and an end coordinate X2 .

Example:

 Line segment A spans from X1==1 to X2==3 Line segment B spans from X1==2 to X2==4 Line segment C spans from X1==3 to X2==5 Line segment D spans from X1==1 to X2==4 ---------------------------------------- Ex1: Line segments that overlap point P==2: A,B and D >>> overlap count==3. Ex2: Line segments that overlap point P==7: None >>> overlap count==0. Ex3: Line segments that overlap point P==3: A,B,C and D >>> overlap count==4. 

Of course, if there are only 4 segments, then the code is simple. However, if there is a huge spatial database of 400 million line segments, the search is very slow.

Are there any algorithms that can efficiently search this list of line segments for the total number of overlaps?

What i see now

• Articles on spatial index search algorithms.
• Tree spacing (looks very promising).
• Segment trees (looks very promising).
• RTrees

Answer 1

If you sort the list by its initial value, and then again (for the same initial value) by length, you will get the roots of an effective algorithm.

 sort the list by starting value for the same starting value, sort by length (longest first) 

Then, when you need the number of line segments that overlap a given point P:

 for a given value p find the points in the list with starting value <= p (binary search - fast) for each starting value, start with the longest length if it spans the point of interest, increment counter if not, go to the next smaller start value keep going until you have reached the smallest starting value 

This is not ideal, but much better than searching through 10M points (although the initial view will take some time, obviously, but you only need to do it once).

Answer 2

sort query points and intermediate endpoints more and more often, in one array; for each point, keep a flag indicating whether this is an interval start, interval end, or request.

Initialize the counter to zero and view the list. Start increases the counter; the end reduces it; the query knows the number of overlapping intervals by reading the counter.

Time (N + M) .Log (N + M) or better if special sorting can be used.

---

If you are not allowed to sort the query points, just sort the endpoints of the interval. In one linear scan, you can calculate the number of overlaps immediately after each endpoint.

For a given query point, you will find the corresponding endpoint by a dichotomous search, therefore, the number of matches.

M.Log (M) + N.Log (M) for M intervals and N query points.

---

If you are not allowed to sort the intervals, just sort the query points.

Process each interval in turn, find the first query point on which it is superimposed, by dichotomous search and increase the counter of all query points that it overlaps.

N.Log (N) + M.Log (N) + O, where O is the total number of interval / query overlaps.

---

If you are not allowed to sort at all, carefully check each request for each interval, NM

Answer 3

Look at spacing trees or segment trees to help solve this problem. This answer contains some good examples of how these methods can help you.

Answer 4

Start with the realization that you cannot do better than O (N), because you need to look at each of the line segments at least once. (where N = number of line segments)

Let there be an array of Line_segments_at, which stores the number of line segments passing through each point.

First we need to initialize this array to 0. Then, when we look at the segment of the i-th line, we need to do:

 for(int j=x1[i];j<=x2[i];j++) Line_segments_at[j]++; 

For each query point k, we can simply return the result as Line_segments_at [k].