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:

• Introduction to bounding volume hierarchies.
  By Herman Haverkort.
  Excerpt from my PhD thesis, Universiteit Utrecht, 2004.
  text

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:

• Efficient c-oriented range searching with DOP-trees.
  By Mark de Berg, Herman Haverkort, and Micha Streppel.
  Computational Geometry, 42(3):250–267, 2009.
  text (or contact me for free access)

A three-dimensional variant is discussed in:

• Box-trees for collision checking in industrial installations.
  By Mark de Berg, Joachim Gudmundsson, and Herman Haverkort.
  Computational Geometry, 28(2-3):113–135, 2004.
  extended text (technical report)

External-memory variants are discussed in:

• The Priority R-Tree: a practically efficient and worst-case-optimal R-tree.
  By Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi.
  ACM Transactions on Algorithms, 4(1):9, 2008.
  text (or contact me for free access)

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):

• Box-trees and R-trees with near-optimal query time.
  By Pankaj Agarwal, Mark de Berg, Joachim Gudmundsson, Mikael Hammar, and Herman Haverkort.
  Discrete & Computational Geometry, 28(3):291–312, 2002.
  text with improved results from PhD thesis slides

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.)

• Cache-oblivious R-trees.
  By Lars Arge, Mark de Berg, and Herman Haverkort.
  Algorithmica, 53(1):50–68, 2009.
  text (or contact me for free access)

The approach based on space-filling curves seems to be more practical and is discussed in:

• Four-dimensional Hilbert curves for R-trees.
  By Herman Haverkort and Freek van Walderveen.
  Journal of Experimental Algorithmics, 16, 2011.
  text (or contact me for free access)

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:

• Quadtrees and Morton indexing.
  By Herman Haverkort and Laura Toma.
  In Encyclopedia of Algorithms, pages 1637–1642, Springer, 2016.
  text

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.

• An edge quadtree for external memory.
  By Herman Haverkort, Mark McGranaghan, and Laura Toma.
  Proc. 12th Int. Symp. on Experimental Algorithms, number 7933 in Lecture Notes in Computer Science (LNCS), pages 115–126, 2013.
  text (or contact me for free access)

• Star-Quadtrees and Guard-Quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions.
  By Mark de Berg, Herman Haverkort, Shripad Thite, and Laura Toma.
  Computational Geometry, 43(5):493–513, 2010.
  text