Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 22.11.2010 02:59, Richard Fabian wrote:
> Although theoretically impossible, it might be practically possible.
> Fabian and Niklas are right in that you cannot hash to similar values,
> and Niklas even has a good idea on how to circumvent the problem, the
> only issue is, you need 2^D where D is the dimensionality of your data
> set. This is probably why Niklas mentions using two hashes.
>
> for a 3D solution (which I think is what you're after), then
> quantisation is key. You could quantise to e (where e is your largest
> snap), and then inside that space, hash the 8 closest different
> positions around your point.

That's the algorithm I described earlier :)

You still have a 2^D factor in there though, which is impractical for 
high dimensions (as are most conventional spatial partitioning methods). 
A different construction based on hashing is Locality Sensitive Hashing 
(LSH) which solves this problem approximately (to a given error 
tolerance) and is significantly faster in practice for data with high 
dimensionality.

-Fabian