Exercises of Chapter 2 (Part 4/7), Computational Geometry

Exercise 2.16. Prove that the point forming the largest angle to the previous edge must be a hull point.


Proof. If it is not, then there's another point with which an edge on the hull can be formed and that edge forms a smaller angle than the angle the point forms, which means the point is on the different side of the the straight line the edge is on than the polygon, therefore the point is outside, contradicting the assumption. □


Exercise 2.17. Show that this algorithm indeed produces the convex hull, closing up the polygon at the starting point.


Proof. The proof can go with two parts, the first part proving that the initial point selected is a hull point and the second being that every subsequent point chosen by the algorithm is actually the hull point adjacent to the previous one. Detail omitted. □

Exercise 2.18. We phrased the gift-wrapping algorithm in terms of angle comparison, which are notoriously slow and numerically unstable when implemented naively. Show that the angle comparison can be replaced by LEFT-OF tests, where LEFT-OF(a, b, c) is true exactly when c is left of the directed line through a and b.


Solution. Suppose the point to which the point to be attached to form the new edge is v, comparing the angles two points a and b form with the edge can be converted to determining LEFT-OF(v, a, b), specifically when the function returns true it means the angle formed by b is greater than that by a.  □

Exercise 2.19. Describe a point set with n points that serves as the worst case for the gift-wrapping algorithm.


Example. A point set that itself constitutes a convex polygon. □


Exercise 2.20. Describe a point set with n points that constitutes the best-case for the gift-wrapping algorithm. What is its time complexity in this case?


Example. Three points in addition to points all inside the triangle formed by them. □


Exercise 2.21. Alter the Graham scan algorithm so that it still works for points in degenerate position.

Solution. Degenerate position for Graham scan is the situation where there are more than one point collinear with the initial point. In this case arranging them by their distance from the initial point in either ascending or descending order will resolve the degeneracy without problem. □

Exercise 2.22. Describe a point set with n points that is the worst-case for Graham scan algorithm.

Example. A boomerang shape with a head vertex at the bottom chosen as the initial point and concave (reflex) points opposite the head between two pointed vertices at the ends of the wings. □

Exercise 2.23. Given a point set S, design an algorithm that finds some polygon (any polygon) whose vertices are precisely S.


Example. A Graham scan without removing points is such an algorithm as required. □

Exercise 2.24. Design a Graham-like algorithm that first sorts the points by their x-coordinate, and then computes the 'upper' and 'lower' hulls respectively. The upper hull is found by repeatedly removing local minima, and the lower hull similarly. Detail the steps needed to realise this high-level description.


Solution. The detailed implementation / pseudo code will be present here shortly. □

Exercise 2.25. Design an algorithm to find the convex hull of a polygon in O(n) time.


Solution. Find the initial point and start going along the boundary of the polygon in specific direction (e.g. counterclockwise) by using techniques similar to what is used in Graham scan algorithm. As it walks through the points on the boundary it removes those concave points by using techniques similar to what is used to eliminate concave points by Graham scan algorithm. It can be proved that it finishes in O(n) time. □