## Geo assignment new work

08 Nov

School of Computer Science
Introduction to Geometric Algorithms
Assignment 4
Semester 2 2016
Due 11:55pm Friday 11 November 2016
Instructions and submission guidelines:
– Answer the following questions. You should answer the questions in enough detail
to convince me that you understand the questions and know how to solve it.
– Make sure that your writing is legible and clear, and the mathematical symbols are
consistent.
– You are allowed to solve the programming questions in three ways:
(1) Matlab 2015a
(2) Python 2.7
(3) Matlab 2015a and C/C++ , where the C++ functions are called from
Matlab using mex files. If you want to use this last option, and do not know how to
write mex files, please check the page:
http://au.mathworks.com/help/matlab/matlab_external/introducing-mexfiles.
html
– You must make sure your code can be run in Linux / Windows / Mac OSX. If you
write your code in pure Matlab (2015a) or Python (2.7), your code should run in those
systems without much trouble, but if you go for the option of Matlab and C/C++, then
you must include a Matlab script that compiles your C/C++ subroutines. You will
lose 10% of marks of this assignment if that compilation script is not included in your
solution and clearly explained.
– Make sure that your codes are well commented and can be executed directly. That
is, without loading any data, setting parameters etc. Such things should be done
within the code.
– Submit your report in pdf and all your codes via the MoodleForum on the course
web page.
– Core Body of Knowledge (CBOK) Areas: problem solving abstract and design,
technology building programming
1. In Fig. 6.2 of the textbook, assume there are n edges.
(1.1) What is the query time complexity to find which slab the query point belongs to
(i.e. search for x_coordinate)? (1.25 marks)
(1.2) Once the slab is determined, what is the query time complexity to find which
cell (in the slab) the query point belongs to (i.e. search for y_coordinate)? (1.25
marks)
(1.3) Binary search can be performed in the question (1.2) because the cells in each
slab are well ordered. The cells are well ordered, because (choose one answer from
below) (1.25 marks)
A) edges do not cross each other;
B) edges are short;
C) edges are long.
2. We know that the search structure for the randomised incremental algorithm has
expected size of O(n), where n are the number of edges (Theorem 6.3 in the
textbook).
(2.1) In the worst-case, the search structure can be beyond linear – this is because
(choose one answer from below) (0.75 marks)
A) cells/trapezoids nodes get duplicated in the search structure;
B) edge nodes get duplicated in the search structure;
C) end point nodes get duplicated in the search structure.
(2.2) In each iteration of the randomised incremental algorithm, adding one line
segment will increase the search structure’s depth by at most how many levels? (0.75
marks)
3. Questions on Voronoi diagram.
(3.1) In a Voronoi Diagram, why every cell is convex? (1 mark)
(3.2) In the sweep line algorithm (a.k.a. Fortune’s algorithm), the sweep line makes
only discrete stops (not continuously). The sweep line will only stop at (choose
multiple answers from below): (0.75 marks)
A) the site points
B) the vertex
C) all bottom points of the circle events
D) bottom points of the true circle events
(3.3) In the sweep line algorithm, when the sweep line meets a site point, it will
kill/remove all (choose one answer from below) (0.75 marks)
A) all site events in the queue
B) all circle events in the queue
C) everything in the queue
(3.4) Each Voronoi vertex is equidistant to at least (choose one answer from below)
(0.75 marks)
A) 4 site points
B) 3 site points
C) 2 site points
D) 1 site point
(3.5) Each point on a Voronoi edge is equidistant to at least (choose one answer from
below) (0.75 marks)
A) 4 site points
B) 3 site points
C) 2 site points
D) 1 site point
(3.6) The number of Voronoi edges is only linear to the number of Voronoi site points
marks)
A) not every pair of site points’ bisector will become a Voronoi edge
B) Euler’s formula
C) the total number of degrees of the Voronoi vertices are two times of the number of
Voronoi edges
(4.1) A bisector of two points is? (0.75 marks)
(4.2) A bisector of a point and a line is? (0.75 marks)
(4.3) A bisector between two line segments consists of many parts, where each part is
either a line segment or a parabolic arc. How many parts at most a bisector between
two line segments consists of? (0.75 marks)
(4.4) The beach line for a Voronoi Diagram with site points consists of (choose one
A) line segments
B) parabolic arc
C) circle arc
(4.5) The beach line for a Voronoi Diagram with sites being line segments consists of
(choose multiple answers from below) (0.75 marks)
A) line segments
B) parabolic arc
C) circle arc
5. To test the roundness of a set of points, we need to know the radius of the inner
circle and the radius of the outer circle.
(5.1) If the centre of the circles is given, we can find the radius of the inner cycle
using (choose one answer from below) (1.25 marks)
A) Voronoi diagram with site points
B) Voronoi diagram with sites being line segments
C) Farthest-point Voronoi diagram
(5.2) If the centre of the circles is given, we can find the radius of the outer cycle
using (choose one answer from below) (1.25 marks)
A) Voronoi diagram with site points
B) Voronoi diagram with sites being line segments
C) Farthest-point Voronoi diagram
(5.3) The centre of the inner and outer circles can be (choose multiple answers from
below) (1.25 marks)
A) vertex of the Voronoi diagram
B) vertex of the Farthest-point Voronoi diagram
C) intersection of two edges — one from the Voronoi diagram and the other from the
Farthest-point Voronoi diagram
6. Your task in this question is to implement the approximate Euclidean Traveling
Salesperson Problem using the Euclidean Minimum Spanning Tree algorithm. The
function is called in the following way:
Tour = ApproxETSP(Pin)
where Pin is a 2xN matrix with all the nodes to be visited in the Euclidean Traveling
Salesperson Problem, and Tour is a 2xN matrix containing the order of nodes to be
visited in the tour. You can use code available (in Matlab and Python) to implement
the Delaunay triangulation, but you need to implement the method to compute the
Euclidean Minimum Spanning Tree algorithm.
Submit the file ApproxETSP.m (if using Matlab) or ApproxETSP.py (if using
Python). (7.5 marks)
Total marks: 25
~~~ Good luck ~~~
by Javen Shi and Gustavo Carneiro, 2016