Voronoi Benchmark

Benchmark Details

From the topological perspective Delaunay triangulation is a dual data structure to the Voronoi diagram, thus libraries that provide Delaunay triangulation construction routines were also included into the benchmark. However, from the computation perspective Voronoi diagram contains more information as it embeds information regarding the coordinates of the centers of the inscribed circles tangent to the three or more input geometries.
The benchmark consists of the two parts:
  1. construction of the Voronoi diagram / Delaunay triangulation of a set of random points uniformly distributed over 32-bit integer grid (voronoi_benchmark_points.cpp)
  2. construction of the Voronoi diagram / Delaunay triangulation of a set of random non-intersecting segments uniformly distributed over 32-bit integer grid (voronoi_benchmark_segments.cpp).

Libraries

Library
Boost.Polygon
CGAL
SHull
Official page
www.boost.org/libs/polygon‎
http://www.cgal.org
http://www.s-hull.org
Algorithm
sweep-line
incremental
sweep-hull
Supported input geometries
points and segments
points and segments
points
Output data structure
Voronoi diagram
Delaunay triangulation
Delaunay triangulation
Complexity
O(N log N)
O(N log N) O(N log N)
Memory usage
O(N)
O(N)
O(N)
Robustness policies
lazy arithmetic, exact predicates, topology analysis
lazy arithmetic, exact predicates, topology analysis
non-robust
Output coordinates precision
128 machine epsilon
no output coordinates
no output coordinates
External dependencies
No
Boost, GMP, MPFR
No

The other known libraries (OpenVoronoi, Triangle, Vroni) will be considered for the inclusion into the benchmark in the future.

System Configuration

Hardware: Intel i5-7600 2.8 GHz, 16GiB RAM.
OS: Ubuntu 13.04 64-bit.
Compiler: GCC 4.7.3.
Libraries and dependencies: Boost 1.54.0, CGAL-4.3-beta1, GMP 5.1.4, MPFR 3.1.2, S-Hull.

Benchmark Results

Random Points Benchmark

Benchmark Points Chart
Test specification
Average construction time (in secs)
Number of Points
Number of Runs
Boost Linux-64
CGAL Linux-64
S-Hull Linux-64
100
10000
0.000206
 0.000073
0.000243
1000
1000
0.002250
0.000753
0.002184
10000
100
0.024100
0.007917
0.030552
100000
10
0.292000
0.084336
0.451913
1000000
1
3.470000
0.902300
6.603814

Random Segments Benchmark

Benchmark Segment Chart
Test specification
Average construction time (in secs)
Number of Segments
Number of Runs
Boost Linux-64
CGAL Linux-64
100
10000
0.002284
0.002985
1000
1000
0.023240
0.032180
10000
100
 0.237700
0.337400
100000
10
2.488000
3.633000
1000000
1
25.00000
39.090000

 
Copyright: Copyright Andrii Sydorchuk 2010-2012.
License: Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)