CODEWITHSUNDEEP
data-structures
Ben Dilts
Ben Dilts

Reputation: 10745

Data structure for a one-dimensional spatial index

I have a large number of objects each representing a numeric range (e.g. [1,3], [2,8], [3,3]). I want to be able to rapidly query for all of the ranges overlapping a given range. This is the one-dimensional equivalent of standard 2D or 3D spatial indexes, such as R-trees.

For example:

Data = [0,1], [1,3], [2,8], [3,3], [5,9]
Query = [2,4]
Output = [1,3], [2,8], [3,3]

I'd like adding items to the structure or removing items from it to usually run in O(log N), and for searching the structure to also usually be O(log N).

Is there a good fit from well-understood standard data structure?

Upvotes: 2

Views: 710

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

An interval tree comes to mind, which is: (description from Wikipedia, image from here)

A tree with each node storing:

  • A center point
  • A pointer to another node containing all intervals completely to the left of the center point
  • A pointer to another node containing all intervals completely to the right of the center point
  • All intervals overlapping the center point sorted by their beginning point
  • All intervals overlapping the center point sorted by their ending point

It allows for O(log n + m) interval intersection queries, where m is the number of intersecting intervals.

You'll have to look at either of the sites for more details regarding construction and querying.

Upvotes: 3

Related Questions