From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-04-23 22:28:38
On Apr 22, 2007, at 5:47 PM, Phil Endecott wrote:
>> This is highly interesting to me. I suppose you're doing this for
>> nearest neighbors of some kind.
> Actually I'm currently just using it to find the subset of a set of
> points that lie within a rectangle. At some point in the future I may
> need to do clustering, at which point nearest-neighbour would
> become useful.
I see. For range searching, kd-trees would be the best in linear
> Some sort of tree (R-Tree, whatever) might sound like a more obvious
> solution to my current problem. I decided to try space filling curves
> instead because they let me exploit the standard containers (e.g.
> std::map); I almost "adapt" the standard 1D container to 2D (or
> potentially higher dimensions).
I had a student do inplace static and dynamic kd-trees: stored
inside a vector, the ordering is key to the organisation of the kd-
tree. The code and documentation are available along with the rest at:
It's unfinished, as I've come to believe that all Theses are
(*sigh*). The thesis itself is accessible at
>> You must be aware of Timothy Chan's
>> paper "Closest-point problems simplified on the RAM", in Proc. 13th
>> ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 472-473,
> I have not found a freely-downloadable version of that.
On Timothy's web page: http://www.cs.uwaterloo.ca/~tmchan/pub.html#ram
I must warn you: Timothy's one of the smartest people around, and
the paper is a deceptively two-page long which could easily fit
eight. But all the code is given in pseudo-code and you don't even
need to understand to program it (although it's nicer to understand,
of course). I've not tried to code it myself, but
> One difference between a 32-bit fixed-point value and a 32-bit
> floating-point value is that in the latter case you "waste" 8 bits for
> the exponent. So for latitude/longitude GPS data you get 256 (or
> 128) times better precision in the same memory space by using fixed
> point. IIRC the difference is between centimetres and metres of
> resolution. In my application, having found the set of points that
> currently visible, their positions are converted to integer screen
> positions for display; at this point it is certainly more efficient to
> not convert to and from floating point again.
Excellent point. Thanks.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk