Delaunay triangulation results

Platform:  SUN Ultra Sparc II with 440 MHz and 256 MBytes
Compiler: g++ 3.0.3
Software: CGAL 2.4 and LEDA 4.4 (current internal versions); latest versions of Triangle and Qhull

Results

 

 

50.000 points 100.000 points 200.000 points
  random in square random in disc lattice random in square random in disc lattice random in square random in disc lattice
Qhull 3.80 3.81 6.48 8.06 8.16 13.72 17.32 17.82 28.98
Triangle 0.64 0.69 1.37 1.52 1.52 1.86 3.60 3.55 4.14
CGAL                  
FE normal 35.90 32.07 48.02 102.47 91.59 139.65 287.29 261.31 -
FE hierarchy 7.25 6.98 53.79 14.07 14.00 153.84 30.70 30.01  
double normal 8.54 7.70 11.48 27.00 23.90 33.27 78.70 71.90 105.24
double hierarchy 1.97 1.91 12.97 4.05 3.97 36.87 8.89 8.76 -
LEDA (Dwyer)                  
rational kernel 2.01 2.04 2.81 4.18 4.21 6.04 8.91 8.71 12.23
float kernel 1.47 1.47 1.19 3.15 3.15 2.59 6.43 6.52 5.55
Our package                  
CGAL FE 3.19 3.20 14.44 6.39 6.53 39.32 13.00 13.15 110.00
CGAL double 0.72 0.70 2.68 1.45 1.49 7.27 3.00 3.02 20.41
LEDA rational k. 1.58 1.61 5.74 3.27 3.33 14.52 6.94 6.86 37.73
LEDA float k. 0.81 0.79 2.58 1.75 1.76 7.22 3.73 3.71 20.87
simple exact 0.63 0.65 6.12 1.33 1.33 13.91 2.74 2.76 33.52
simple double 0.60 0.61 2.11 1.25 1.28 5.83 2.60 2.60 15.92

Notes

All CGAL tests were performed with the Simple Cartesian Kernel.
FE: Filtered_exact<double, leda_real>

The generated points are not permuted.


Last modified on 2002-05-31  by M. Bäsken.