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!

Daniel Lemiresays: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.

JeffEsays: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).

Chechosays:Where is the KD-Tree applet?… can you send it to me please? Thanks!