[mlpack-git] [mlpack/mlpack] Neighbor Search - Incorrect bound. (#642)

[Ryan Curtin]

Yes, if you think of a space tree that breaks everything post it. :)

The proof works even for non-ball bound trees: regardless of the shape of the bound, lambda represents the furthest distance of any descendant point to the center. So even if the bound is a hyperrectangle, all of the points in that bound are contained in a ball of radius lambda (sorry I don't know how to add Unicode characters on my phone!). This applies for the child also, and it must be true that B_c is contained in B_q because all descendant points of N_c are contained in the set of all descendant points of N_q.

Even if the hyperrectangle bound is loose for a kd-tree node it doesn't end up mattering for the sake of the bound B_2, because for the calculation of B_2 we are using the implicit ball bounds B_q and B_c.

I hope I've written that clearly. let me know if not. :)

I will fix the paper write up tomorrow, thanks for pointing out the error.

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/issues/642#issuecomment-221722904
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160525/7a74d133/attachment.html>