## CS507: Computational Geometry

Instructor:

McGill University

### Exam 2 - Solutions - 2000

#### Question 1:

Run the Jarvis gift-wrapping convex hull algorithm, except before closing the hull after h iterations keep sweeping to find the first point on the second layer and so on. The algorithm runs in O(n2) worst-case time (since h = n)

#### Question 2:

See Question 1 of exam 1999.

#### Question 3:

a) If a point pi is on the hull, there is an empty halfplane L defined by a line through the point. Take the ray from the point pi, orthogonal to L, into the halfplane. Any point on this ray is closer to pi than to any other site, thus the voronoi region V(i) is unbounded.
Now, if a cell V(i) is unbounded, then similarly we can argue that there exists a ray passing through pi and that there exists a line L .... there exists a halfplane...

b) In a furthest point voronoi diagram V every 3 neighboring points define a circle containing all the points. The furthest point Delaunay triangulation D is obtained by connecting the vertices that are neighbors in V. Thus, the vertices of a triangle in D are 3 neighboring vertices in V, and hence a circle passing through the vertices of any triangle in D will contain all the points.

#### Question 4:

This corresponds to constructing a convex hull of points in the dual. If you didn't cover duality, don't worry about it.