DELAUNAY TRIANGULATION BENCHMARKS

Denis Špelič - Franc Novak - Borut Žalik

   In this communication we propose an initial set of 2D Delaunay triangulation benchmarks for checking the correctness of algorithms and discovering possible flaws. A tool for verification of the generated triangulation is provided. The tool reports typical errors like the existence of unused points, missing edges, non-Delaunay triangles or degenerated triangles. While the tool has been primarily conceived for the verification of the implemented algorithms it may also be used for their debugging in the early design phase.

Keywords: computational geometry, Delaunay triangulation, benchmarks

[full-paper]