Area tree

A range tree ( English range tree ) is a data structure for storing a quantity of points in k-dimensional real space . It is used in computer science in the area of algorithmic geometry and efficiently supports orthogonal area inquiries. ${\displaystyle \mathbb {R} ^{k}}$

field of use

Such data structures are used in geographic information systems . Here they are used to search for geographic objects. Geographic information systems manage the spatial coordinates of these objects. The area tree now subdivides (partitions) the objects into subsets depending on their coordinates. This means that the search for a specific object can later be narrowed down to a small area and thus significantly accelerated. Such data structures are also known as index structures .

Mathematical description

In the simplest case, i.e. the one-dimensional area tree is a normal binary search tree. In general, the k-dimensional range tree is defined recursively: ${\displaystyle \mathbb {R} ^{1}}$ ${\displaystyle T^{1}}$ ${\displaystyle T^{k}}$

Let { } be the coordinate axes of the ${\displaystyle x_{1},x_{2},\dotsc ,x_{k}}$ ${\displaystyle \mathbb {R} ^{k}}$

• First construct a 1-dimensional area tree for the coordinate axis , i. H. for 1-dimensional points that result from cutting off the back coordinates. Each node is assigned an interval that extends from the smallest to the largest number that is stored in the subtree of the node. ${\displaystyle T^{1}}$ ${\displaystyle x_{1}}$ ${\displaystyle k-1}$
• Recursively construct for each inner node of the one -dimensional area tree from the -dimensional points that are contained in the subtree as roots and result from cutting off the first coordinate. ${\displaystyle v}$ ${\displaystyle T^{1}}$ ${\displaystyle (k-1)}$ ${\displaystyle T_{v}^{k-1}}$ ${\displaystyle (k-1)}$ ${\displaystyle v}$
• Connect the node of the with the corresponding one with the help of a pointer ${\displaystyle v}$ ${\displaystyle T^{1}}$ ${\displaystyle T_{v}^{k-1}}$

The area tree constructed in this way supports orthogonal area queries in

${\displaystyle O(n(\log n)^{k-1})}$ Storage space

${\displaystyle O((\log n)^{k}+a)}$Time, where the size of the answer is, i.e. H. the number of points in the query rectangle. By fractional cascading the request time can be improved. ${\displaystyle a}$ ${\displaystyle O((\log n)^{k-1}+a)}$

See also

• Quadtree , Kd-Baum , UB-Baum , R-Baum , Gridfile as alternatives

literature

• Rolf Klein: Algorithmic Geometry 2nd Edition. Springer-Verlag, Berlin Heidelberg 2005, ISBN 3-540-20956-5 .