Assignment 1: Convex Hull - ML

The convex hull of a set of points is the set of points which induce the smallest convest polygon around the points of the set. There are many different mechanisms for solving the convex hull problem, but one of the most efficient algorithms (in amortized analysis) is known as Quick Hull. This algorithm is innately recursive, and is probably the easiest algorithm to implement in ML.

Details

Write a function quick_hull: (real * real) list -> (real * real) list. This function takes a list of tuples representing 2-d cartesian coordinates, and returns a list of tuples representing 2-d cartesian coordinates. This function should return the list of points that are on the convex hull of the input set of points.

You may write any additional functions you need to solve the problem. However, for each function you write you must include a comment explaining the purpose of the function. For example, the comment for the above function could be "Returns the list of points on the convex hull of the input list of points".

Algorithm

The Quick Hull algorithm is an inherently recursive definition that relies on the fact that certain points can be computed that MUST be on the convex hull. At a broad level, the algorithm involves:

1. Find two points which must be on the convex hull. These two points are those with the maximum and minimum x-coordinates. If there are several points with the same maximum or minimum coordinates, the tie is broken using the maximum/minimum y-coordinates.
2. Compute the line that passes through these two points. This line divides the set of points into two sets, which are recursively processed by:
   1. Find the point that is farthest from the base line that created the set. That point MUST be on the convex hull.
   2. Compute two lines, one that joins the end points of the base line to this new point. This creates 3 sets: The points inside the triangle, the points to the left of the triangle, and the points to the right of the triangle. Recursively process the points on the left and right sets until they are empty. The points inside the triangle cannot possibly be in the set.

Grading

Your programs will be graded on a scale split across both functionality (80%) and style (20%). Style points are earned from proper documentation (described above) and appropriate use of pattern-matching and the built in curried functions. If a function could be written using fold and/or map, you should use these functions. If a function could be written using pattern matching, you should also use this technique.

Submission

Submit your .sml file to inquire by Feb. 19^th, 2016.

Notes

Assignments are to be done individually. You may ask class members, lab assistants, and others for help with system questions (e.g., "How do I start the ML interpreter?" or "How do I get a printout of my program?") or general information about a topic covered in class (e.g. "What is the symbol for boolean AND?") provided you can do so without divulging or receiving information specific to the solution of the assignment problem. You may not discuss any aspect of the design or coding of a program with anyone except the instructor. See the syllabus for more information.