  We present a novel approach to perform agglomeration of polygonal and
polyhedral grids based on spatial indices. Agglomeration strategies are a key
ingredient in polytopal methods for PDEs as they are used to generate
(hierarchies of) computational grids from an initial grid. Spatial indices are
specialized data structures that significantly accelerate queries involving
spatial relationships in arbitrary space dimensions. We show how the
construction of the R-tree spatial database of an arbitrary fine grid offers a
natural and efficient agglomeration strategy with the following
characteristics: i) the process is fully automated, robust, and
dimension-independent, ii) it automatically produces a balanced and nested
hierarchy of agglomerates, and iii) the shape of the agglomerates is tightly
close to the respective axis aligned bounding boxes. Moreover, the R-tree
approach provides a full hierarchy of nested agglomerates which permits fast
query and allows for efficient geometric multigrid methods to be applied also
to those cases where a hierarchy of grids is not present at construction time.
We present several examples based on polygonal discontinuous Galerkin methods,
confirming the effectiveness of our approach in the context of challenging
three-dimensional geometries and the design of geometric multigrid
preconditioners.
