COMP20007 Design of Algorithms

COMP20007 Design of Algorithms School of Computing and Information Systems The University of Melbourne Assignment 1: Convex Hull Due: 11:59 PM Thursday April 11th Introduction A set S in the plane is called convex if it satises the following property: for every pair of points p; q 2 S the line segment between them pq is also in the set S (i.e., pq S). One problem that comes up time and time again in areas such as computational geometry is the problem of nding the smallest convex set S which contains all points in some other set X. This set is called the convex hull of X. When given some set of points we can describe the convex hull S by listing the points which make up the vertices in the boundary of the convex hull. Figure 1: A set of points and the boundary of their corresponding convex hull, which is coloured in grey. Levitin Section 3.3: Closest-Pair and Convex-Hull Problems by Brute Force provides a more compre- hensive description and discussion of the convex hull problem. In this assignment you will implement an algorithm to compute the convex hull of a given set of points. The assignment consists of 3 (three) coding tasks (Part A, Part C and Part F) and 4 (four) analysis tasks (Part B, Part D, Part E and Part G). 1 Tasks Part A: Point Orientation Let p0; p1; p2 be three points in the plane. If p2 is left of the line segment p0p1, then we write Left(p0; p1; p2). If p2 is right of the line segment p0p1, then we write Right(p0; p1; p2). If three points are on the same straight line, then we say that (p0; p1; p2) are collinear. (a) p0 p1 p2 p3 (b) p0 p1 p2 p3 Figure 2: (a) In this example p2 is Left of p0p1, while p3 is Right of p0p1. (b) Here p0; p1; p2 and p3 are all collinear points, so we say that each 3-subset of the four points are collinear e.g., p0; p2 and p3 are collinear. Your task is to complete the implementation of orientation() in convex-hull.c which takes three points (p0, p1 and p2) and returns `l' if p2 is Left of p0p1, `r' if p2 is Right of p0p1 or `c' if p0; p1 and p2 are Collinear. Your function must run in O(1) time. Hint: check out Appendix A which describes a number of useful vector operations. Part B: Checking for Convexity Let P = (p0; : : : ; pn􀀀1) be a sequence of n points in the Euclidean plane (R2). Assume you have been given the following algorithm: function isConvex(p0; : : : ; pn􀀀1) for i 0 to n 􀀀 1 do if Right(pi; p(i+1) mod n; p(i+2) mod n) then return false return true Update: the \return true" was previously incorrectly indented so that it was inside the for loop. This has been corrected. Does the algorithm above correctly determine if P is the boundary of a convex polygon in counter- clockwise order? Explain your answer. The Inside Hull Algorithm A polygon is called simple if it has no self intersections. We describe a convex hull algorithm, called InsideHull and abbreviated with IH, that computes the convex hull of a simple polygon P = (p0; p1; : : : ; pn􀀀1), with points pi 2 R2 and its corresponding edges pipi+1. The points are ordered in counterclockwise order. 2 Although our denition of a simple polygon doesn't exclude successive points being collinear, Inside- Hull assumes that this is not the case. InsideHull uses a double ended queue abstract data type to represent the convex polygon it constructs. A double ended queue is abbreviated to deque and it has the following operations: push to the top of the deque pop from the top of the deque insert to the bottom of the deque remove from the bottom of the deque The top and bottom of a deque c are indexed by ct and cb respectively. In the following algorithm the deque c gives rise to the convex hull C = hcb; cb+1; : : : ; ct􀀀1; cti. The algorithm is as follows. Parts of the algorithm denoted by : : : are not complete and will require you to ll them in. function InsideHull(Polygon) : : : conrm the input is valid : : : if Left(p0; p1; p2) then C new deque hp2; p0; p1; p2i else C new deque hp2; p1; p0; p2i : : : while i < n do Get next point pi if Left(ct􀀀1; ct; pi) and Left(cb; cb+1; pi) then i i + 1 Continue while Right(ct􀀀1; ct; pi) do Pop ct from C Push pi to C while Right(cb; cb+1; pi) do Remove cb from C Insert pi into C i i + 1 : : : Note that during the algorithm, the deque C contains the points of the partial convex hull (which is completed by the end of the algorithm) in counter-clockwise order. At the beginning of each outer while loop cb and ct refer to the same point, and this point will always be the most recent point added to C. Part C: Deque Data Structure Implement a Deque abstract data structure and complete the denitions of the following functions in deque.c: new deque() free deque() deque push() deque insert() 3 deque pop() deque remove() deque size() It is up to you to decide on which underlying data structure will be used for your Deque. All of the operations described above must run in constant (O(1)) time1. Update: free deque() may run in linear (O(n)) time. Part D: Deque Analysis Explain your deque implementation and the decisions you made. Describe the time complexities of the four main operations (push, pop, insert, remove) and how these time complexities are achieved. Part E: Inside Hull Tracing Run the following example by hand and provide the points contained in the deque at each step of the algorithm. Be clear about which end of your deque is the top and which is the bottom. The points are provided to InsideHull in alphabetic order, starting with point A. A B C D E F H G Part F: Inside Hull Implementation Implement the C function inside hull() that takes a polygon consisting of n points and computes the points of its convex hull. The polygon will be provided as an array of n points named points, and the points will appear in counter-clockwise order. Your function should store the points which make up the convex hull in the array hull, which will have enough memory for at least n points. These points should be stored in counter-clockwise order, and the rst and last points should not be the same. This will mean the number of points in hull will be one fewer than the size of the deque C at the end of the algorithm. The number of points stored in hull should be returned. If an error occurs return INSIDE HULL ERROR. If three consecutive points are collinear return COLLINEAR POINTS and don't complete the algorithm (make sure you free any memory you have allocated before you return). Note: You may assume that the input we will use to test your program will either have collinear points occurring consecutively or no collinear points at all. Note that the points across the array boundary (e.g., Polygon[n 􀀀 1]; Polygon[0]; and Polygon[1]) are considered consecutive. 1We require constant case on average, i.e., constant amortised runtime. This means you may choose to use some sort of resizable array, as long as the resizing isn't being performed during each operation 4 Part G: Inside Hull Analysis The best algorithms we have for computing convex hulls for a general set of n points are O(n log n), if they are not output sensitive2. Identify the basic operations in the InsideHull algorithm and use this to determine the time complexity of InsideHull, give your answer in Big-Oh notation. Explain how you arrived at this answer. Does this contradict the statement about runtimes above? Explain why it does or does not. Completing the Coding Tasks We have provided the skeleton for this project which includes the following les: main.c { The entry point to the program, and the functionality which deals with command line input and output. Do not change this le. point.h, point.c { Provides the Point struct and related functions. You may add to this module if you need additional functionality, but don't change existing code. convex-hull.h, convex-hull.c { Here is where you will implement orientation() and inside hull(). You may add to the header le don't change existing function signatures. deque.h deque.c { Here is where you will implement your Deque data structure. You may add to the header le don't change existing function signatures. Makefile { provides make targets all (to compile the program), clean (to delete the .o les and the executable) and submit (which creates submission.zip including all les in the directory). You should add to this Makele if you want us to compile your program in another way, or if you add other les. To compile the program run make. This will create an executable a1. Feel free to add any additional .c/.h les, but make sure you add these to your Makefile as well. For information about how the program a1 runs, and the command line options, please see Appendix B: Using The Command Line Tool. Your code will be compiled and tested on the School of Engineering's Linux Servers so make sure you compile and test your code thoroughly on dimefox before submission. For information on how to login to dimefox see the Workshops section of the LMS. Please try this early and often, being unable to access dimefox is not grounds for an extension or other considerations. Completing the Analysis Tasks You should create a PDF le analysis.pdf with your answers to Parts B, D, E and G. You should aim to write no more than 2 pages. Justify all your answers and provide answers as asymptotic complexity classes (e.g., O; ; ). To receive full marks the bounds should be tight, for example if an algorithm is an n2 algorithm O(n2) will receive full marks, while O(n3);O(2n);O(n!); etc. will not. Marking The total number of available marks for this assignment is 10 (ten), and this assignment is worth 10% of your grade in this subject. 2An output sensitive algorithm's runtime depends on the size of the output as well as the size of the input, in this context it would mean that the runtime is dependent on the number of points which are part of the convex hull.