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 satis es 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; : : : ; pn1) be a sequence of n points in the Euclidean plane (R2). Assume you have been
given the following algorithm:
function isConvex(p0; : : : ; pn1)
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; : : : ; pn1), with points pi 2 R2 and its corresponding
edges pipi+1. The points are ordered in counterclockwise order.
2
Although our de nition 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; : : : ; ct1; 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)
: : : con rm 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(ct1; ct; pi) and Left(cb; cb+1; pi) then
i i + 1
Continue
while Right(ct1; 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 de nitions 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 Make le 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.