Periodic Boundary Conditions (Third time's a charm)

[cavemanloverboy]

Periodic boundary conditions are required for several applications, including cosmology where these boundary conditions are employed to simplify the calculation of gravity.

There are two ways (that I know of) to implement periodic queries for a kDTree. The first is quite expensive in space/memory, but theoretically may provide faster queries (remains to be seen, as it is also a larger tree). The second is cheaper in mem, but involves multiple queries:

1. Make 3^K-1 copies of the data and build a tree using the 3^K images. Accept queries only on the original image.
2. Build a tree on a single image, and do up to 2^K queries on the subset of images which the query point is closest to, if necessary. To give a 3D example: if you measure a kNN with some distance d, and you are less than d away from the side of a box, you must re-query at the query's periodic image on the other side of the box. If you are close to two box sides, you must check each side, but also the image that touches only the box edge. If you are close to three box sides, you must check the 3 side images, the 3 edge images, and the image whose corner touches only one corner of the original box (2^3-1 checks). The kNNs are then given by the first k points of the union of all of these query results; you can alternatively share a candidate container across these queries.

In FNNTW, I implemented 2, as 1 is too expensive in my view. Method 2 is also the least invasive, as this only changes the query process and not the build process (other than a check that all data points are in the bounding box you claim is periodic). A potential optimization here that is not in FNNTW is to make this a short-circuiting check -- after a query, and after updating new_best_kth, you can check to see if you are still close to the other edges and return early if not.

This issue is intending to open the floor and discuss the implementation strategy to be used in kiddo.