School of Computer Science

The University of Adelaide

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

(instead of quadratic). This is because (choose multiple answers from below) (0.75

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. Please answer the following questions.

(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

answer from below) (0.75 marks)

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

## Geo assignment new work

08
Nov