CGAL users discussion list

[Sergey Simonchik <>]

Hello everybody,

I work on comparing robustness of convex hull 3D algorithms, so first thanks 
all the CGAL developers: I have one more implementation to compare. But I 
have some questions:

1) Why does implementation of quickhull algorithm (CGAL::convex_hull_3) has 
such strange
performance results? For testing purpose code snippet from 
CGAL-3.2.1/examples/Convex_hull_3/quickhull_3_ex.C was taken. Only point 
generation was changed from distribution in sphere to distribution on sphere. 
Here results:
 - processing of 10000 points on sphere takes 31594 ms;
 - 20000 points takes 94375 ms
 - 30000 points takes 170953 ms
 - 40000 points takes 286484 ms
 - 50000 points takes 409719 ms.

 It seems, that algorithm doesn't related to algorithms with  O(n*log(n)) 
complexity on given distribution, because constant C in C*n*log(n) expression 
has such relative rates: 1.389, 1.160, 1.223, 1.121 (relative rate implies 
the following ratio: C_{i+1} / C_i).

2) Why does facet orientations differ in quckhull (ccw in to see to facet 
from outside) and randomized incremental algorithms (cw)?

Thanks in advance.
Sergey.