Boost logo

Boost :

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-04-22 00:25:07

On Apr 19, 2007, at 3:25 PM, Phil Endecott wrote:
> I'd also like to mention that I have been using this type to implement
> a 2D set<point> container using space filling curves.

This is highly interesting to me. I suppose you're doing this for
nearest neighbors of some kind. 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 imagine (this was my first thought when reading Chan's
paper) that everything can be wrapped into a functor that computes
the order along the curve. Is this the approach you're
implementing? I'd be interested to hear your thoughts / experience /
esp. your setup (why you are interested in this in the first place).
You can reply to the list if you think it's of general interest, or
to me directly.

Re: the original topic of this thread, I really don't see the point
of fixed-point arithmetic for this, though, it seems to me point
coordinates could be computed in floating point, then rounded/scaled
to integers for inserting into the set<point>. Iow, the fixed-point
coordinates are likely simply representational, not used in
computations. Unless you're dealing with moving points, and even

Btw, in Dr Dobb's I saw an article recently which I really didn't
understand. Seemed like the author rediscovered quad-trees. Seems
like a functor for comparing along space-filling curves would also
make a great paper for Dr Dobb's / CUJ. Cheers,

Herve Bronnimann

Boost list run by bdawes at, gregod at, cpdaniel at, john at