Problem Based Benchmark Suite

Delaunay Triangulation (DT):

Given a set of points in 2 dimensions generate the Delaunay triangulation.

Input and Output File Formats

The input needs to be in the 2d points file format and the output needs to be in the Triangles format. Triangles can be in any order but the coordinates need to be in the same order in the output as in the input. The output can include additional points beyond the original points. These extra points must appear in the output after the original points and the resulting triangles must be a Delaunay triangulation of all points. The extra points can be used, for example, to insert points at the corners of a bounding box around the original points.

Default Input Distributions

Each distribution should be run for n=10,000,000. The point sets should have no degeneracies and standard geometric predicates (e.g., line side and in circle) should be resolvable with double precision floating point arithmetic. The purpose of this benchmark is not to compare state-of-the-art exact geometric predicates. The two tests are given equal weight.
last modified 15:18, 05 Jun 2012

This project has been funded by the following sources:
Intel Labs Academic Research Office for the Parallel Algorithms for Non-Numeric Computing Program,
National Science Foundation, and
IBM Research.