kd-tree applet
k-dimensional trees are a clever way to select all points in a rectangle using O(sqrt(n)+k) time where n is the total number of points and k is the number of points in the range. I usually don’t care for applets as a way to illustrate results (though I have two on my own web site doing just that!), but this kd-tree applet is a great trick. I post this here because I want to use it in a course if I ever have to teach this concept. The applet is in the public domain, but was written by Jacob Marner.
I resisted posting the applet here, because I know Java can crash some browsers or create other trouble. Sad. Java is an ok language and I really wish it would work in the browser.
Follow me on twitter!
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).
Comment by JeffE — 25/1/2006 @ 18:53
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.
Comment by Daniel Lemire — 25/1/2006 @ 19:02
Where is the KD-Tree applet?… can you send it to me please? Thanks!
Comment by Checho — 16/3/2006 @ 15:01