Problem Based Benchmark Suite (2020)

Delaunay Refinement (DR):

Given a Delaunay triangulation in 2 dimensions, return a Delaunay triangulation that includes all original points plus additional points such that no triangle has an angle smaller than a threshold Theta.

Input and Output File Formats

Both the input and output need to be in the Triangles file format. The input must be a valid Delaunay triangulation of its points. The output must include all input points, plus any number of additional points, and must be a valid Delaunay Triangulation of all its points.

Default Input Distributions

Each distribution should be run for n=2,000,000. For this benchmark the input triangulation is generated using a Delaunay triangulation on various point distributions. These triangulations are generated using the PBBS code for Delaunay triangulations, which also adds in a small number of boundary points beyond the original input points. The point sets are non degenerate.

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

  uniform -s -d 2 <n> <tmpname>
  delaunay -o <filename> <tmpname>

• (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> <tmpname>
  delaunay -o <filename> <tmpname>