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.

    Reply

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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks: 

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

Or, you can subscribe without commenting.