Finding All Intervals That Overlap a Point

Question

Consider a large set of floating-point intervals in 1-dimension, e.g.

 [1.0, 2.5],                1.0 |---------------|2.5

 [1.5, 3.6],                      1.5|---------------------|3.6

 .....

It is desired to find all intervals that contain a given point. For example given point = 1.2, algorithm should return the first interval, and if given point = 2.0, it should return the first two interval in the above example.

In the problem I am dealing, this operation needs to be repeated for a large number of times for a large number of intervals. Therefore a brute-force search is not desired and performance is an important factor.

After searching about it, I saw this problem is addressed using interval skip list in the context of computational geometry. I was wondering if there is any simple, efficient C++ implementation available.

---

EDIT: To be more precise about the problem, there are N intervals and for M points, it should be determined which intervals contain each point. N and M are large numbers where M is larger than N.

Answer 1

Suggest using CGAL range trees:

Wikipedia says interval trees (1-dimensional range trees) can "efficiently find all intervals that overlap with any given interval or point".