Daniel Lemire's blog

, 2 min read

kd-tree applet

3 thoughts on “kd-tree applet”

  1. 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.

  2. JeffE says:

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

  3. Checho says:

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