  Searching spatial data is an important operation for scientific simulations
which are performed mostly with periodic boundary conditions. An R-Tree is a
well known tree data structure used to contain spatial objects and it is
capable of answering to spatial searching queries in an efficient way. In this
paper, a novel method to construct an R-Tree considering periodic boundary
conditions is presented. Unlike existing methods, the proposed method works
without any kind of extra objects or queries. Moreover, because this method
reduces the volume of bounding box for each node under the periodic boundary
conditions, it is expected to increase the overall efficiency. While the
extension of an R-Tree is presented in this work, this method is not only
applicable to an R-Tree but also to other data structures that use axis-aligned
bounding boxes with periodic boundary conditions. The implementation is
available on GitHub.

Data Structures and Algorithms