title: nearest neighbor - k-d tree - wikipedia proof
body: <p>On the <a href="http://en.wikipedia.org/wiki/Kd-tree#Nearest_neighbor_search" rel="noreferrer">wikipedia entry for k-d trees</a>, an algorithm is presented for doing a nearest neighbor search on a k-d tree.  What I don't understand is the explanation of step 3.2.  How do you know there isn't a closer point just because the difference between the splitting coordinate of the search point and the current node is greater than the difference between the splitting coordinate of the search point and the current best? </p>
  
  <blockquote>
    <p>Nearest neighbor search Animation of
    NN searching with a KD Tree in 2D</p>
    
    <p>The nearest neighbor (NN) algorithm
    aims to find the point in the tree
    which is nearest to a given input
    point. This search can be done
    efficiently by using the tree
    properties to quickly eliminate large
    portions of the search space.
    Searching for a nearest neighbor in a
    kd-tree proceeds as follows:</p>
    
    <ol>
    <li>Starting with the root node, the algorithm moves down the tree
    recursively, in the same way that it
    would if the search point were being
    inserted (i.e. it goes right or left
    depending on whether the point is
    greater or less than the current node
    in the split dimension).</li>
    <li>Once the algorithm reaches a leaf node, it saves that node point as
    the "current best"</li>
    <li>The algorithm unwinds the recursion of the tree, performing the
    following steps at each node:
         1. If the current node is closer than the current best, then it
    becomes the current best.
         2. The algorithm checks whether there could be any points on
    the other side of the splitting plane
    that are closer to the search point
    than the current best. In concept,
    this is done by intersecting the
    splitting hyperplane with a
    hypersphere around the search point
    that has a radius equal to the current
    nearest distance. Since the
    hyperplanes are all axis-aligned this
    is implemented as a simple comparison
    to see whether the difference between
    the splitting coordinate of the search
    point and current node is less than
    the distance (overall coordinates)
    from the search point to the current
    best.
               1. If the hypersphere crosses the plane, there could be
    nearer points on the other side of the
    plane, so the algorithm must move down
    the other branch of the tree from the
    current node looking for closer
    points, following the same recursive
    process as the entire search.
               2. If the hypersphere doesn't intersect the splitting plane,
    then the algorithm continues walking
    up the tree, and the entire branch on
    the other side of that node is
    eliminated.</li>
    <li>When the algorithm finishes this process for the root node, then the
    search is complete.</li>
    </ol>
    
    <p>Generally the algorithm uses squared
    distances for comparison to avoid
    computing square roots. Additionally,
    it can save computation by holding the
    squared current best distance in a
    variable for comparison.</p>
  </blockquote>