CGAL users discussion list

[Joao Dinis <>]

Hi all,

I've found intriguing run times while computing 3D convex hulls of sites
on the surface of a sphere.
I expected that the CGAL::convex_hull_3 function would be faster than
CGAL::convex_hull_incremental_3, since it implements the quick hull
algorithm.
I did modify (slightly) the files 'quickhull_3.cpp' and
'incremental_hull_3.cpp' from the CGAL examples directories generate a
variable number of sites and obtained the following timings to process
10000 sites at random positions:

1) convex_hull_3             -> 24.6 seconds,
2) convex_hull_incremental_3 -> 4.51 seconds.

Is this behaviour correct?
Does the quick hull algorithm performs so bad on a degenerate
configuration as sites on the surface of a sphere?

I'm using CGAL-3.5.1 on a Pentium D @ 3GHz, with gcc 4.4.1.
Other than generating 'n' sites, the files are as supplied by the
distro.
That means CGAL::Homogeneous<CGAL::Gmpz> on file
'incremental_hull_3.cpp' and 
CGAL::Exact_predicates_inexact_constructions_kernel on file
'quickhull_3.cpp'.


Thanks in advance,

-- Joao Dinis