Stack Overflow
Stack Overflow

Questions tagged [range-tree]

A Range Tree is Data Structure that allows fast range queries, such as [4, 5] x [-2, 0]. Use for questions related to implementation/study of this tree.

Sourcing Wikipedia:

A range tree on a set of 1-dimensional points is a balanced binary search tree on those points. The points stored in the tree are stored in the leaves of the tree; each internal node stores the largest value contained in its left subtree. A range tree on a set of points in d-dimensions is a recursively defined multi-level binary search tree. Each level of the data structure is a binary search tree on one of the d-dimensions. The first level is a binary search tree on the first of the d-coordinates. Each vertex v of this tree contains an associated structure that is a (d−1)-dimensional range tree on the last (d−1)-coordinates of the points stored in the subtree of v.

23 questions
6
votes
3 answers

Most efficient way to select point with the most surrounding points

N.B: there's a major edit at the bottom of the question - check it out Question Say I have a set of points: I want to find the point with the most points surrounding it, within radius (ie a circle) or within (ie a square) of the point for 2…
Nick Bull
  • 9,518
  • 6
  • 36
  • 58
5
votes
1 answer

Modeling a Node in a RangeTree

I am currently implementing a 2D Range Tree. I am having trouble coming up with a plausible model (in Java) for my Node class. A node in the tree may have any of the following: midrange value, right and left child pointer, subtree, data pointer…
Andriy Drozdyuk
  • 58,435
  • 50
  • 171
  • 272
5
votes
1 answer

Clear And Efficient 3D Range Tree Implementation

I'm working on this project where I have to search for objects in 3d space, and efficiency is a huge concern, I think Range Tree is perfect for what I'm trying to do, Interval Tree would also work but I'm not going to delete anything from the tree,…
user1880907
  • 173
  • 1
  • 7
4
votes
0 answers

High Dimensional Interval Tree

I am with a problem where a high dimension interval tree may help. I can understand how a unidimensional interval tree works. But I can't see how should be implemented in a higher dimension. Interval Tree and Range Tree The explanation at Wikipedia…
StudentKiddo
  • 41
  • 2
4
votes
3 answers

interval range tree datastructure c++

I have a requirement where I have to update the color of a graphical frontend based on some attribute value.The attribute value has different ranges ....say -30 to -45, -60 to -80 and so on.....So, I needed a datastaructure where I could store…
basav
  • 1,475
  • 12
  • 20
3
votes
2 answers

Range/Segment Tree Ruby

I am looking for a range or segment tree implementation in Ruby. I could not find any sample or gem available. Does anyone have a sample code ? Thanks,
Paul
  • 31
  • 1
3
votes
1 answer

Range Trees: why not save space by default?

Suppose you have a set S of unique points on the 2-dimensional plane. Now, you are expecting a bunch of questions in the form of "is point p present in S?" You decide to build a Range Tree to store your S and answer this question. The basic idea…
alisianoi
  • 2,003
  • 3
  • 31
  • 46
3
votes
1 answer

How to search in a Range Tree?

I read several slides, like this one's last page, where the describe the search algorithm. However, I have a basic question. The data lie in a 2D space. I first build a Binary Search Tree based on the x value of the points. Every inner node holds a…
gsamaras
  • 71,951
  • 46
  • 188
  • 305
3
votes
1 answer

How to do high dimensional range query with fixed range?

I have about 10^4 points in 7 dimensional space. For a certain application, I need to make ~10^6 range queries on this input to find all the points that lie inside a given range. In this application, all the queries use the same range size. What is…
Ashwin Nanjappa
  • 76,204
  • 83
  • 211
  • 292
2
votes
2 answers

Why is the number of sub-trees gained from a range tree query is O(log(n))?

I'm trying to figure out this data structure, but I don't understand how can we tell there are O(log(n)) subtrees that represents the answer to a query? Here is a picture for illustration: Thanks!
elihar
  • 109
  • 1
  • 13
2
votes
2 answers

Is range tree widely used in spacial search problems?

I am looking for some data structures for range searching. I think range trees offer a good time complexity (but with some storage requirements). However, it seems to me that other data structures, like KD-trees, are more discussed and recommended…
Alaya
  • 3,287
  • 4
  • 27
  • 39
1
vote
1 answer

Algorithm for finding grid cells contained in arbitrary rotated rectangle (rasterizing)

I'm looking for an algorithm that can compute all grid cells occupied by an arbitrary rectangle in 2d space in a defined area. The rectangle is defined by it's 4 corner coordinates. In the picture below I marked two of them as red, the coordinates…
sollniss
  • 1,895
  • 2
  • 19
  • 36
1
vote
0 answers

Counting queries for 2d range trees using fractional cascading

Are there any libraries that provided 2d range trees with fractional cascading, that have O(log n) complexity for range counting queries (i.e., O(log^(d-1) n) for d dimensions)? One promising coded snippet I found is…
Nick Bull
  • 9,518
  • 6
  • 36
  • 58
1
vote
1 answer

Priority Search Tree confusion

The only reasonable slide set I found is this, which in page 15 says, for building: Sort all points by their x coordinate value and store them in the leaf nodes of a balanced binary tree (i.e., a range tree) Starting at the root, each node…
gsamaras
  • 71,951
  • 46
  • 188
  • 305
1
vote
1 answer

Range tree implementation

I'm trying to implement a Range tree but I'm really confused, Here is my text: Now suppose that I have a tree like this: And I want to find the points between 14 and 19. V_Split would be 17 here, and moving from 17 to 14, according to algorithm, I…
MoNo
  • 307
  • 4
  • 15
1
2