, 1 min read
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.