Re: Acceleration Structures For Vertex Snapping

On 11/19/2010 2:43 PM, Jeff Russell wrote:
> It's not *really* O(1), since you can have an arbitrary number of
> vertices in a single hash cell (worst case would be the entire mesh).
> Only perfect hashing would allow for O(1) worst case behavior.

What do you mean by "not *really* O(1)"? Big O notation just means we're 
talking about asymptotic complexity, it doesn't have to be worst-case 
(hence "expected O(1)").

 > It's
 > really O(n) worst case, but since the n is divided by such a large
 > constant in practice it is still a very fast approach.

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). 
Their worst-case is definitely linear and the constant isn't tiny as 
everyone who's ever used a bad hash function knows :). Worst-case and 
average-case analysis are just different things.

-Fabian

------------------------------------------------------------------------------
Beautiful is writing same markup. Internet Explorer 9 supports
standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
Spend less time writing and  rewriting code and more time creating great
experiences on the web. Be a part of the beta today
http://p.sf.net/sfu/msIE9-sfdev2dev
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list