I've just read about R-Trees:

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle.

This seems to be a Bounding Volume Hierarchy (BVH) with axis-aligned bounding boxes (AABBs):

A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree.

[...]

One of the most commonly used bounding volumes is an axis-aligned minimum bounding box.

Both allow overlapping nodes.

I've learned about BVHs in a Computer Graphics lecture and about R-trees by a professor who is mainly working on databases. So it might be that different communities developed the same datastructure independently.

Is there any difference between R-Trees and BVHs?

  • R-Trees seem to be balanced. They seem to be constructed bottom-up (starting with a single point, inserting new points), whereas BVHs are constructed Top-down (starting with all points). – Martin Thoma Apr 24 '16 at 15:02
up vote 7 down vote accepted
+50

Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is useful.

However, bounding-volume hierarchy is a very general notion. When designing a bounding-volume hierarchy data structure in practice, it is extremely important to decide what kind of bounding volumes to use. The bounding volume can be any geometric shape: circle, hexagon, square, trangle or rectangle. It is important to keep this bounding volume very simple (we want it to be easy to store, rather than a complicated geometrical shape) and easy to fit other objects in (we don't want to waste a lot of free space in the bounding volume, as it can cause exhaustive search.

Quote from [1],

Below, I will first explain what a bounding-volume hierarchy is and how it is used. After that, I will explain what issues have to be addressed when designing a bounding-volume hierarchy. I will then focus on a particular class of bounding volume hierarchies, namely R-trees, and give an overview of our results on Rtrees.

R-tree is a class of BVH data structures that uses rectangles as bounding-volume. Rectangles are easy to store and they can cover other shapes easily. It is noted that R-tree is not the only class of BVH and there are other BVHs proposed using different shapes. Even among R-trees, there is a variety.

This data structure is important for different communities: computer graphics, computational geometry, database and others. All of them need to deal with situations where they need to query a set of geometrical objects (or vectors).

[1] Herman Johannes Haverkort, Results on geometric networks and data structures, 2004.

  • Accept and 50 reward for the reference. If you add the relevant part ("Below, I will first explain what a bounding-volume hierarchy is and how it is used. After that, I will explain what issues have to be addressed when designing a bounding-volume hierarchy. I will then focus on a particular class of bounding volume hierarchies, namely R-trees, and give an overview of our results on Rtrees.") you will get another +1 :-) – Martin Thoma May 11 '16 at 20:06
  • @MartinThoma Got that, however, R-tree is not the only class of BVHs. There are others such as circles. Even among R-trees there are varieties. – orezvani May 12 '16 at 1:17

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.