Problem Based Benchmark Suite

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.
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.