< Back

Assignment 3: Convex Hull - Prolog

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. For this assignment, there is no restriction on the algorithm to use. If you can figure out ANY mechanism for computing the convex hull, you are fine.


Details

Write a predicate convexHull(AList, TheHull). This predicate should evaluate to True when TheHull is the set of points on the convex hull of the points specified in AList.

You may write any additional predicates you need to solve the problem. You should make effective use of pattern matching as necessary. You should avoid singleton variable warnings as much as possible as well. Your predicates need not function well when some parameters are not bound, but you should include a comment for each predicate explaining which variables must be bound to work correctly.


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 If a predicate could be written using pattern matching, you should also use this technique.


Submission

Submit your .sml file to inquire by April 18th, 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 Prolog 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 defining a predicate?") 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.