title: Nearest neighbor search with periodic boundary conditions
body: <p>In a cubic box I have a large collection points in R^3. I'd like to find the k nearest neighbors for each point. Normally I'd think to use something like a k-d tree, but in this case I have periodic boundary conditions. As I understand it, a k-d tree works by partitioning the space by cutting it into hyper planes of one less dimension, i.e. in 3D we would split the space by drawing 2D planes. For any given point, it is either on the plane, above it, or below it. However, when you split the space with periodic boundary conditions a point could be considered to be on either side!</p>
  
  <p>What's the most efficient method of finding and maintaining a list of nearest neighbors with periodic boundary conditions in R^3? </p>
  
  <p>Approximations are not sufficient, and the points will only be moved one at a time (think Monte Carlo not N-body simulation).</p>