1. Pastel
  2. PastelGeometry
  3. Geometric algorithms
  4. Range searching
  5. Range searching in a range tree

Range searching in a range tree

Back to Range searching

Range searching in a range tree takes time, where is the number of points in the tree, is the number of reported points, and is the number of orders. The time complexity of range searching degrades gracefully as points become equivalent with respect to the orders. For example, if the points are all equivalent in the first orders, for , then range searching takes only time.

Files

Range search in a range tree