This might not be a right place to ask this but I'll try in hope someone can provide at least a reference to a solution.
My impasse is the following situation. On one hand i have a list of overlapping intervals like this:
[1..2] [1..3] [2..7] [1..5] [4..5] [3..10] ... # each interval has a unique pair of start and stop coordinates
on the other i have a list of points:
4 6 8 ...
Task is for each point in my list, to find all intervals that overlap is. What i am currently doing is extremely stupid. I mapped the points and then i roll-out each interval (loop from x..y in each interval) and check if there is any point equal to a position in my hashmap. if it is, i simply associate a key ( point in my hashmap to a value (which is a vector of all intervals that overlap that point). My aim is to be able to answer multiply queries once the index (map) is created. Problem is that for a large number of intervals this index construction becomes extremely slow (especially when the average overlap between interval increases ). Could anyone provide hint on how to reduce algorithm construction runtime for this problem?