Boost logo

Boost :

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,
>> 2002.
> I have not found a freely-downloadable version of that.

On Timothy's web page:
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
> maybe
> 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
> are
> 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, gregod at, cpdaniel at, john at