<p>You are right, I failed to consider that it is possible that a child hyperrectangle's implicit bounding ball can lie not entirely withing the parent hyperrectangle's implicit bounding ball.  It's easy to rework the proof I wrote to be correct and that comes out with the error correction 2 \lambda(N_q) - \lambda(N_c) (that is, we are subtracting just one times the furthest descendant distance of N_c, not two), but this is a less tight bound that the idea you suggested with B_{aux}(.).  So I guess that I can conclude that my bound is incorrect and there isn't a better choice I can see than to go with your solution.  Thanks for pointing all of this out.</p>

<p>When you apply this bound, it would be interesting to see how much it helps performance; that could easily be tracked by running <code>mlpack_knn</code> with the <code>-v</code> option, and looking at the number of base cases on a handful of datasets before and after the change.  If you want to do this, feel free; if not, that's no issue, I'll do it. :)</p>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/issues/642#issuecomment-222153406">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFLcU9TRdEZwsX4BV-lZqk5oulTwAks5qFviYgaJpZM4Iksxi">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFEmuJZ5TqA7C4Kak4Oz6OsjMU7XMks5qFviYgaJpZM4Iksxi.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
  <link itemprop="url" href="https://github.com/mlpack/mlpack/issues/642#issuecomment-222153406"></link>
  <meta itemprop="name" content="View Issue"></meta>
</div>
<meta itemprop="description" content="View this Issue on GitHub"></meta>
</div>