<p>Hi Ryan,<br>
Thank you very much for taking the time to write that proof. This is becoming really interesting!</p>

<p>I am not sure about:<br>
"The ball of radius lambda(N_c) centered at the center of the node N_c lies entirely within the ball of radius lambda(N_q) centered at the center of the node N_q."<br>
I agree that this is true for trees that consider "ballbound", but that is not true for different bounds such as "hrectbound" used in KDTrees.<br>
The ball of radius (diagonal_of_rectangle / 2) centered at the center of a rectangle will not include the balls of the subrectangles resulting of splitting the original rectangle at the middle.</p>

<p>However, with actual KDTree implementation, we do not have any problem because points are only included in leaf nodes, so the optimization of using rho instead of lambda is never considered.</p>

<p>How are R-Trees implemented? Do they include points in non-leaf nodes? I will read about them.</p>

<p>I have an idea of a space tree where the B2 bound could fail. I will try to think about it and I let you know.</p>

<p>Thanks!</p>

<p>PD: A simple detail about the proof, in ecuations (8) and (9), should be (lambda(N_q) - lambda(N_c)) instead of (lambda(N_q) + lambda(N_c)). In case you want to use it in the future.</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 or <a href="https://github.com/mlpack/mlpack/issues/642#issuecomment-221717687">view it on GitHub</a><img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFB_aGKiDC54r2VlmWEvBnjXt5Ry9ks5qFMMTgaJpZM4Iksxi.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-221717687"></link>
  <meta itemprop="name" content="View Issue"></meta>
</div>
<meta itemprop="description" content="View this Issue on GitHub"></meta>
</div>