From: Clifford Heath <no@...>
Date: 2008-01-21T08:40:00+09:00
Subject: Re: kD-Trees implementation

Marcin Raczkowski wrote:
> There are reaserch papers that descripbe O(nlogn) instead of (nlog^2n) 
> algorithms but They are usually full of complex math and 20-50 pages 
> long. Also one that i could understand Is based n pointers and 
> interlinked lists and it's kinda hard to implement in Ruby

The wikipedia page for kdtrees references an o(n) median-finding algorithm
in a book compiled by Cormen and others. I have the book, and the algorithm
doesn't look too scary. I might have a go at implementing it. But in any
case, the exact median is only needed if you demand an exactly-balanced tree.
Subsequent insertions will unbalance the tree anyhow in most cases, so it's
probably not necessary.

The algorithm for finding the i'th lowest entry given in the book is as follows.
(copyright, fair use provisions allow posting):

The SELECT algorithm determines the ith smallest of an input array of n > 1 elements by
executing the following steps. (If n = 1, then SELECT merely returns its only input value as
the ith smallest.)
1. Divide the n elements of the input array into ⌊n/5⌋ groups of 5 elements each and at
most one group made up of the remaining n mod 5 elements.
2. Find the median of each of the ⌈n/5⌉ groups by first insertion sorting the elements of
each group (of which there are at most 5) and then picking the median from the sorted
list of group elements.
3. Use SELECT recursively to find the median x of the ⌈n/5⌉ medians found in step 2.
(If there are an even number of medians, then by our convention, x is the lower
median.)
4. Partition the input array around the median-of-medians x using the modified version of
PARTITION. Let k be one more than the number of elements on the low side of the
partition, so that x is the kth smallest element and there are n-k elements on the high
side of the partition.
5. If i = k, then return x. Otherwise, use SELECT recursively to find the ith smallest
element on the low side if i < k, or the (i - k)th smallest element on the high side if i >
k.

That's it, not too scary.

Clifford Heath.