Upper Hull: a classic problem (based on Convex Hull)

Problem description

The convex hull is the smallest convex set that encloses all of the points of a given a list of points. Please check Wikipedia or other resources for more details. The upper hull problem is then only the upper half of the convex hull. More details on this problem and its implmentation in Baffier et al.

Here, we assume that the points are in the plan (2D space) and sorted in increasing values of their x-coordinate.

Instance generator

An instance generator is provided as examples/upperhull/generateInputUpperHull.cpp. If the provided CMake file CMakeLists.txt is used as described in the Installation (Build) page, an executable to generate Upper Hull instances will be built.

The generateInputUpperHull executable can be called as follows. The random values indicates the minimum and maximum coordinates of the randoms points generated.

path_to_executable/generateInputUpperHull path_to_file/file_name stacktype size space rand_min rand_max

Specific examples can be generated as follows.

// Upper hull:  for point with min=3.5 and max=74  (n=1000, p=50)
path_to_executable/generateInputUpperHull path_to_file/file_name 1 1000 50 3.5 74

Basic usage

If we suppose the path to the previous generated instance is stored in the variable filePath, then a simple utilization of the library would be as such:

// Create the StackAlgo object and its associated stack to compute the Upper Hull
Instance upperHull(filePath);
// Actually computes the Upper Hull
upperHull.run();
// Print the actual state of the stack at the end of the algorithm
upperHull.println();

Example with command line

One instance is available in this repository for the UpperHull problem. It can be executed as easily as

// We assume the user is at the root directory of the library
build_directory/upperhull8 examples/upperhull/instances/testFileUpperHull1000p50.txt