Most of my work on geometric data structures is on bounding-volume hierarchies, such as R-trees; three papers are on quadtrees.
A bounding-volume hierarchy is a tree structure on a set of geometric objects (the data objects). Each object is stored in a leaf of the tree. Each internal node stores for each of its children u an additional geometric object V(u), that encloses all data objects that are stored in descendants of u (a minimum bounding rectangle, for example). In other words, V(u) is a bounding volume for the descendants of u. Bounding-volume hierarchies can be used to do many types of queries on the set of data objects. For example, all data objects that intersect a query window Q can be found by recursively visiting all nodes whose bounding volumes intersect Q. For a more elaborate introduction to bounding volume hierarchies, see:
We do theoretical and experimental research into the construction of bounding-volume hierarchies such as R-trees and similar data structures with good query times. We have been exploring two approaches to building bounding-volume hiearchies: approaches based on binary space partitions (BSP's), and approaches based on space-filling curves.
The most comprehensive and general treatment of our BSP-based approach in two dimensions can be found in:
A three-dimensional variant is discussed in:
External-memory variants are discussed in:
| If you consider implementing the Priority R-tree in practice, check out my work with Freek van Walderveen on four-dimensional Hilbert curves (see below), which includes additional experiments on the Priority R-Tree with different data sets. |
The following paper laid the groundwork for all of the above, introducing the basic ideas and lower bounds (but each of the above papers is self-contained, one does not need to read the following paper first):
Several open questions remain. We prove that there are sets of n objects in the plane, such that for any hierarchy of axis-aligned bounding rectangles on this set, there are points that lie outside any object's bounding rectangle, but inside Ω(√n) rectangles of the hierarchy. However, if the individual objects' bounding rectangles are pairwise disjoint, a hierarchy exists such that any point lies in only O(log² n) bounding rectangles. Can the latter bound be improved to O(log n)? Can we do better than Ω(√n) if the objects are disjoint but their bounding boxes are not?
We also tried to take our work for external memory one step further by coming up with a cache-oblivious solution. Unfortunately, if you try to work out the “hidden constants” in the theoretical work in this paper, you may find that we did not manage to prove that our cache-oblivious R-trees are anywhere close to efficient in practice. (This does not mean they are not practical, only that we did not manage to prove so. Whether they are practical or not, I do not know.)
The approach based on space-filling curves seems to be more practical and is discussed in:
For more theoretical results on space-filling curves that may be relevant to the construction of bounding-volume hierarchies, see the page on recursive tilings and space-filling curves.
The following article gives a brief summary of important results on quadtrees:
The following papers present a simple and I/O-efficient way to build so-called linear quadtrees for subdivisions in the plane. The resulting data structures can be used for efficient point location queries, range reporting queries and map overlay operations.