Introduction to Computational Geometry, Spring 2020

Michael Kazhdan


Assignment 2: Convex Hulls (2D)

Due on March 25 (Wednesday) @ 11:59 pm


Announcements


Overview

In this assignment you will implement the Quick-Hull and Graham's algorithms for computing the convex hull of a set of points in two-dimensions.

Getting Started

You should use the code (Assignments.zip) as a starting point for your assignment. You will need to add your code where it says:
/////////////////////////////
// You need to implement this
/////////////////////////////

After you download the files, the first thing to do is compile the program.


How the Program Works

The program runs on the command line. It uses the number of samples specified on the command line to create a random set of points in 2D. It then computes the convex hull and outputs the results to the specified file.

What You Have to Do


Evaluation


Code will be evaluated based on correctness (and efficiency).

Submission


Please email your implemented source code to me. (The code should compile under Windows/Linux and should not require any additional libraries.)
HOME