Problem Based Benchmark Suite (2020)

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.

• (1) Points selected at random uniformly within a unit circle.

  uniform -s -d 2 <n> <filename>

• (1) Points selected at random from the Kuzmin distribution. This is a 2d version of the 3d Plummer distribution with points highly concentrated around the origin, but some points far off.

  plummer -d 2 <n> <filename>