Computational geometry benchmarks

A few remarks

The test platform was a Sun Ultra-II 440 MHz with 256 MB RAM.
I used the g++ compiler 3.0.4; the software was compiled with -O option.
The tested LEDA version was 4.4 BETA, the CGAL version was 2.4.
For the CGAL tests I compiled with -NDEBUG and I switched pre/postconditions and assertions off.
More results (and results for different machines/compilers) will follow in the future.
All results are in seconds. If not stated otherwise, we used a range of 10000 for generating x,y,z point coordinates.


Results 2d convex hull

Algorithms:

IC    - incremental construction
RIC  - randomized incremental construction
float - LEDA float kernel was used
rat   - LEDA rat kernel was used
scd  - Simple_cartesian kernel and number type double

Note that all measured times are the times for running a function with a list container (LEDA or STL list).
The time for creating this list is not measured.


Input (generator / #points) LEDA-RIC float LEDA-RIC rat LEDA-IC float LEDA-IC rat GEOMLEP-Quickhull float GEOMLEP-Quickhull rat GEOMLEP-Quickhull/Graham float GEOMLEP-Quickhull/Graham rat CGAL convex_hull_2 (scd) CGAL bykat (scd) CGAL eddy (scd) CGAL graham/andrew (scd)
square (100000) 0.31 0.57 0.1 0.27 0.12 0.5 0.14 0.57 0.16 0.12 0.19 0.27
square (200000) 0.69 1.17 0.18 0.74 0.25 1.32 0.26 1.37 0.54 0.25 0.4 0.6
square (500000) 2.13 3.01 0.48 1.89 0.71 3.59 0.67 3.71 1.53 0.67 1.05 1.62
disc (100000) 0.34 0.53 0.11 0.33 0.17 0.5 0.16 0.59 0.12 0.13 0.22 0.25
disc (200000) 0.69 1.42 0.25 0.73 0.39 1.05 0.49 1.07 0.28 0.27 0.44 0.55
disc (500000) 2.18 3.15 0.63 1.84 1.18 2.83 1.2 2.78 0.72 0.81 1.13 1.62
near circle (100000) 0.62 1.27 0.29 0.97 0.88 2.14 1.02 2.22 0.27 0.35 0.48 0.28
near circle (200000) 1.31 2.51 0.61 1.7 1.96 4.37 2.37 4.92 0.58 0.7 0.99 0.6
near circle (500000) 3.66 6.48 1.53 4.42 7.43 11.84 8.35 14.07 1.48 1.87 2.53 1.64
lattice (100000) 0.3 0.57 3.51 9.86 0.09 0.7 0.08 0.71 0.21 0.12 0.2 0.18
lattice (200000) 0.72 1.17 11.65 29.34 0.2 1.5 0.2 1.52 0.49 0.26 0.4 0.42
lattice (500000) 2.2 3.13 49.1 116.95 0.6 3.85 0.6 3.94 1.22 0.62 1.03 1.1

Click on the small pictures to view the charts of the benchmarks:

Square.
Disc.
Near circle.
Lattice.

The second table shows comparisons between various CGAL kernels; the used number type is double, the results are in seconds.
The homogeneous kernels got an additional third coordinate of 1.

Input (generator / #points) Cartesian convex_hull_2 Cartesian bykat Cartesian eddy Cartesian graham/andrew Simple_cartesian convex_hull_2 Simple_cartesian bykat Simple_cartesian eddy Simple_cartesian graham/andrew Homogeneous convex_hull_2 Homogeneous bykat Homogeneous eddy Homogeneous graham/andrew Simple_homogeneous convex_hull_2 Simple_homogeneous bykat Simple_homogeneous eddy Simple_homogeneous graham/andrew
square (100000) 0.29 0.2 0.29 0.5 0.17 0.13 0.21 0.27 0.34 0.26 0.32 0.6 0.22 0.19 0.24 0.34
square (200000) 1.07 0.4 0.53 1.21 0.52 0.24 0.41 0.6 1.32 0.51 0.6 1.48 0.75 0.34 0.47 0.82
square (500000) 3.04 1.06 1.4 3.56 1.5 0.6 1.0 1.6 3.64 1.37 1.55 4.2 2.0 0.9 1.2 2.17

The third table again shows comparisons between various CGAL kernels; this time the used number type is Filtered_exact parametrized with double and leda_real, the results are in seconds.
The homogeneous kernels got an additional third coordinate of 1. The results with 500000 points are not shown here because for the Homogeneous kernel my computer started swapping for this input and the program crashed after a while.

Input (generator / #points) Cartesian convex_hull_2 Cartesian bykat Cartesian eddy Cartesian graham/andrew Simple_cartesian convex_hull_2 Simple_cartesian bykat Simple_cartesian eddy Simple_cartesian graham/andrew Homogeneous convex_hull_2 Homogeneous bykat Homogeneous eddy Homogeneous graham/andrew Simple_homogeneous convex_hull_2 Simple_homogeneous bykat Simple_homogeneous eddy Simple_homogeneous graham/andrew
square (100000) 0.8 0.73 0.75 0.78 0.65 0.68 0.67 0.55 0.93 0.54 0.53 1.05 0.76 0.46 0.49 0.84
square (200000) 1.83 1.55 1.55 1.81 1.39 1.38 1.4 1.23 2.23 1.15 1.1 2.39 1.76 0.99 0.99 1.83

Conclusion/remarks:

CGAL is doing well in the 2d convex hull benchmarks, but all tested libraries have quite good results. GEOMLEP is very fast if the output is small, but it is quite slow if the output is large.
LEDA-IC shows its quadratic worst case running time on some unfriendly input point sets (that's why the standard algorithm in LEDA is RIC).


Results 3d convex hull

Algorithms:

LEDA         - incremental construction + some preprocessing
GEOMLEP - mix of quickhull and LEDA
float           - LEDA float kernel was used
rat             - LEDA rat kernel was used
scd            - Simple_cartesian kernel and number type double
sc_fe_dr     - Simple_cartesian kernel, number type Filtered exact parametrized with double and leda real

Input (generator / #points) LEDA float LEDA rat GEOMLEP float GEOMLEP rat CGAL Quickhull (sc_fe_dr) CGAL incremental (sc_fe_dr) CGAL Quickhull (scd) CGAL incremental (scd)
ball 20000 0.61 0.72 0.29 0.5 1.04 2.33 0.55 1.14
ball 40000 1.45 1.56 0.5 0.88 2.14 4.41 1.13 1.94
ball 60000 2.15 2.47 0.75 1.21 3.52 7.66 1.83 2.9
ball 80000 3.35 3.48 1.03 1.67 5.55 9.4 2.55 4.02
ball 100000 4.17 4.23 1.21 2.11 6.58 11.93 3.47 6.94
cube 20000 0.38 0.49 0.17 0.27 0.55 1.69 0.22 0.88
cube 40000 0.79 0.95 0.28 0.49 1.25 4.29 0.35 1.37
cube 60000 1.28 1.49 0.43 0.7 1.86 4.89 0.6 3.02
cube 80000 1.64 1.99 0.53 1.09 3.3 5.43 0.89 4.03
cube 100000 2.07 2.25 0.62 1.2 3.29 10.79 1.11 4
on sphere 2000 0.18 0.23 0.18 0.3 - - 1.08 0.34
on sphere 4000 0.36 0.5 0.38 0.61 - - 4.22 0.75
on sphere 6000 0.57 0.78 0.6 0.93 - - 9.47 1.23
on sphere 8000 0.78 1.12 0.82 1.28 - - 17.28 1.74
on sphere 10000 1 1.43 1.07 1.62 - - 26.7 2.34

Click on the small pictures to view the charts of the benchmarks:

In Cube.
In Ball.
On Sphere.

Conclusion/remarks:

CGAL Quickhull is doing well when the output is small, but it is very slow, when the output is large.
I could not even finish some benchmarks when using CGAL (see table).


Results 2d simple triangulation

Algorithms/Data structures:
LEDA uses a sweep to construct the 2d simple triangulation
and a dynamic parametrized GRAPH for storing the planar embedding.
CGAL uses its Triangulation data type and (randomized ?) incremental construction.
Apart from the CGAL Triangulation data type we test as well the triangulation hierarchy.

Input (generator / #points) LEDA rat LEDA float CGAL "normal" (scd) CGAL hierarchy (scd) CGAL "normal" (sc_fe_dr) CGAL hierarchy (sc_fe_dr)
square 20000 0.42 0.32 8.01 1.23 32.65 5.71
square 40000 0.97 0.64 28.23 3.1 122 13
square 100000 2.52 1.82 156 11.7 - -
disc 20000 0.42 0.36 8 1.15 36.2 5.2
disc 40000 0.84 0.66 29 3.02 104.9 12.6
disc 100000 2.53 1.81 160.2 10.8 - -
near circle 20000 0.43 0.29 0.83 1.06 3.46 3.02
near circle 40000 0.81 0.53 2.67 2.51 10.3 8.27
near circle 100000 1.9 1.29 12.19 7.5 42 18.5
lattice 20000 0.38 0.3 0.19 0.78 0.33 3.34
lattice 40000 0.85 0.54 0.37 2.1 0.66 9.46
lattice 100000 2.18 1.44 0.95 7.28 1.65 33.6

Conclusion/remarks:

LEDA is at the moment faster than CGAL for most input point sets, but the
hierarchy helps a lot to speed up the calculation of the triangulation in CGAL.
Unfortunately there are input point sets where the hierarchy is slower than the "normal" triangulation.


Results 2d Delaunay triangulation

The next table shows comparisons between various CGAL kernels for Delaunay triangulation computation; the used number type is double, the results are in seconds.
The homogeneous kernels got an additional third coordinate of 1.

Input (generator / #points) Cartesian kernel Simple_cartesian kernel Homogeneous kernel Simple_homogeneous kernel
square (50000) 10.08 7.7 11.54 9.35
square (100000) 30.8 24.1 35.1 29.1

This time the used number type is Filtered_exact parametrized with double and leda_real.

Input (generator / #points) Cartesian kernel Simple_cartesian kernel Homogeneous kernel Simple_homogeneous kernel
square (50000) 30.6 28.8 13.6 11.25
square (100000) 90.7 83.6 42.7 35


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