# 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

 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

 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