# [SciPy-Dev] Periodic Boundary Conditions and kd-trees

Jacob VanderPlas vanderplas@astro.washington....
Thu Mar 1 18:05:38 CST 2012

```Patrick,
I think you're correct that the KD implementation in scipy would have to
be pretty extensively modified to work with periodic boundary
conditions.  The new ball tree implementation I've been working on
minimal additional code - you could even use it as-is with a periodic
metric defined in python.

The implementation needs a fair bit of work before it will be ready for
inclusion in scikit-learn, and I haven't had the time to work on it
recently, but you can take a look!  Let me know if you have any
questions on that.
Jake

Patrick Varilly wrote:
> Hi Emanuele,
>
> Thanks for your comments, I will definitely look into cover trees and
> ball trees, since these are new to me.  As an aside, though, "distance
> to the minimum image" satisfies the triangle inequality, since its the
> natural metric for points on tori (easiest to see for 2D periodic
> boundary conditions).  What breaks down is the idea that if you have
> three points with x-coordinates x1 < x2 < x3, then d(2,3) < d(1,3)
> [but d(1,3) <= d(1,2) + d(2,3) remains true].  This is what might
> cause trouble with kd-trees, but my thinking was that if I could
> phrase all kd-tree operations in terms of answering the question "what
> is the minimum distance between x and region Y of space", then the
> only difference between PBCs and open boundary conditions is how you
>
> Best,
>
> Patrick
>
> On Thu, Mar 1, 2012 at 4:45 PM, Emanuele Olivetti
> <emanuele@relativita.com <mailto:emanuele@relativita.com>> wrote:
>
>     Hi Patrick,
>
>     The general kd-tree algorithm works for distance functions that
>     are metric
>     (e.g. triangle inequality holds). As far as I know the current
>     SciPy implementation
>     of kd-tree works for Euclidean distance only. There is another
>     similar algorithms,
>     the BallTree, which is implemented in scikits-learn [0] and it is
>     very fast (Cython)
>     but again for Euclidean distance only.
>     Recently Jake VanderPlas, the author of scikits-learn BallTree
>     started to
>     extend it to other distances and set up a templated code for
>     inserting the distance
>     you like [0]. This might be of interest to you but pay attention
>     distance because it might not be metric.
>
>     Recently I started to extend a pure-Python implementation of the
>     cover-tree
>     algorithm which is another very efficient data structure for fast
>     nearest neighbor [1].
>     The implementation is slow in building the cover-tree - at the
>     moment -
>     and very fast during queries but the good thing is that it works
>     for general
>     metrics. You might be interested in this as well. Unfortunately I
>     am swamped in
>     other activites so my improvements are very very slow now. It
>     should be usable though.
>
>     Best,
>
>     Emanuele
>
>     [0]: https://github.com/jakevdp/pyDistances
>     [1]: https://github.com/emanuele/PyCoverTree
>
>
>     On 03/01/2012 03:31 PM, Patrick Varilly wrote:
>>     Hi,
>>
>>     I am writing to ask for some guidance / advice with modifying
>>     SciPy's kd-tree code.  I'm writing a Python code with SciPy that
>>     deals with a set of points in 3D.  For each one of them, I need
>>     to list which other points are within a distance r.  The trouble
>>     is that the points are in a periodic box, so "distance between x
>>     and y" means "distance between x and closest image of y".
>>     Currently, I'm using code that does a dumb O(N^2) brute force
>>     search, and was about to code up a cell list to replace it (cell
>>     lists are commonly used for this in molecular dynamics codes).
>>     However, KD-trees seem like a much more generally useful
>>     structure for this, and SciPy already implements kd-trees for
>>     open boundary conditions.  Since periodic boundary conditions
>>     (PBCs) are quite common in most molecular simulation and analysis
>>     codes, having PBC-aware kd-trees would be useful to a large
>>     number of users.
>>
>>     I am thinking of modifying scipy.spatial.kdtree to adapt it to
>>     periodic boundary conditions, and would like to ask if anyone
>>     else has done this or something similar to it already.  If not,
>>     is there any advice that can be had on potential problems that
>>     can come up that I should know about before embarking on this
>>     modification?  My goal would be to contribute this change back to
>>     SciPy, so any advice on what the most SciPythonic way of exposing
>>     PBCs in the kd-tree interface would also be welcome.
>>
>>     Thanks,
>>
>>     Patrick
>>
>>
>>     _______________________________________________
>>     SciPy-Dev mailing list
>>     SciPy-Dev@scipy.org <mailto:SciPy-Dev@scipy.org>
>>     http://mail.scipy.org/mailman/listinfo/scipy-dev
>>
>
>
>     _______________________________________________
>     SciPy-Dev mailing list
>     SciPy-Dev@scipy.org <mailto:SciPy-Dev@scipy.org>
>     http://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
```