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.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

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

Leave a Reply

Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com.

You may subscribe to this blog by email.