Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Jeff R. <je...@8m...>]

Okay, worst case is different from average case, granted. But since the cell
size in this case is fixed (related to snap distance), the number of mesh
vertices that cell will contain varies with n. An example: if your mesh was
evenly tessellated in space, the number of vertices in a single cell would
be n / k, where k is the number of cells your mesh intersects. That makes
finding the closest vertex an "n / k" operation, which is definitely not
constant time. That is what I meant when I said it was O(n). It would only
be O(1) average case if we had a "vertices per cell" limit we could somehow
enforce, but we don't.

No, that's not true. Hash tables are fast in practice because they do a
> small number of reasonably fast operations in the average case, not
> because they do a large number of operations in a magically ultra-fast
> fashion (which would be the O(N) with tiny constant that you decribe).
>

There's no magic, an O(N) algorithm does not necessarily do N operations.
Hash tables are fast because they run in O(n / k) time, where k is
comparable to or larger than n. If you make k a function of n, as is often
done, then it becomes constant time average case.

-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com