Problem Based Benchmark Suite

Convex Hull (CH):

Given a set of points in 2 dimensions return the set of points on the convex hull in sorted order.

Input and Output File Formats

The input needs to be in the 2d points file format. The output needs to be in the sequence file format and must contain the integer index of each of the points in the convex hull. These indices need to be in sorted order with the leftmost point first (minimimum x value).

Default Input Distributions

Each distribution should be run for n=10,000,000. The weights used for average time are given in parentheses. The distribution on the perimeter of a circle is given a lesser weight to account for the fact it is much more costly, and therefore would dominate without a weight adjustment.
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.