22nd January 2006, 2 min read kd-tree applet 3 thoughts on “kd-tree applet” Daniel Lemire says: January 25, 2006 at 7:02 pm Thanks. I meant to type O(sqrt{n} + k) but wrote O(log{n} + k) instead, thanks for pointing out the typo. Thanks also for giving out the general result. Aren’t you busy attending SODA or something like it? I guess it must be over. JeffE says: January 25, 2006 at 6:53 pm Actually, kd-trees require O(n^{1-1/d} + k) time to report the k points in a d-dimensional box. For rectangles in the plane, that’s O(sqrt{n} + k). Checho says: March 16, 2006 at 3:01 pm Where is the KD-Tree applet?… can you send it to me please? Thanks!
Thanks. I meant to type O(sqrt{n} + k) but wrote O(log{n} + k) instead, thanks for pointing out the typo. Thanks also for giving out the general result.
Aren’t you busy attending SODA or something like it? I guess it must be over.
Actually, kd-trees require O(n^{1-1/d} + k) time to report the k points in a d-dimensional box. For rectangles in the plane, that’s O(sqrt{n} + k).
Where is the KD-Tree applet?… can you send it to me please? Thanks!