Problem Based Benchmark Suite (2020)

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.

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

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

• (5) Points selected at random from the Kuzmin distribution.

  plummer -d 2 <n> <filename>

• (1) Points selected at random uniformly on the perimiter of a unit circle.

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