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

Exercise 2.11. Find a way to order points in the plane without moving them into general position.


Solution. For all points lying on the same vertical line, assign indices to them based on their y-coordinates so they are kept apart and can get picked up in order. □


Exercise 2.12. Alter the incremental algorithm so that it still works for point sets which may have two or more points with the same x-coordinate, without rotating the set into general position.


Solution. The algorithm is modified in such a way that the above method is used whenever points it applies to are encountered. □


Exercise 2.13. Adjust the incremental algorithm so that it still works for point sets that may include three or more collinear points.


Solution. Depending on whether points on edges can be preserved, we treat the points on detected on the tangent accordingly. The key is the edges of the current convex comprise edges visible, edges invisible and edges aligned with one of the tangents. □

Exercise 2.14. Given three points (a, b, c), detail a computation that will decide if they form a clockwise or a counterclocksise triangle.


Solution. One way (which may not be most efficient) is to check the cross product (outer product) of vector ab and ac which determines whether swiping from ab to ac goes clockwise or counterclockwise. □

Exercise 2.15. In the incremental algorithm, find a method to search for the tangent line that leads, overall, to a time complexity of O(n) rather than O(n²). Notice that this improves the speed of the algorithm to O(n log n).

Solution. The improved algorithm would keep track of the edge with the minimum inclining slope on the upper boundary and the edge with the minimum declining slope (here minimum means with minimum absolute value) on the lower boundary. It then should check the lines that connect the right ends of these edges and the point being added and decide whether and from where tangent points would be searched for and the hull thus gets updated. This is believed to help improve the speed with neither comprehensive coverage on the special cases involved in this algorithm nor detailed proof of its being able to attain O(n) being given here for the moment (elaborate algorithm will be given shortly for this exercise as well as for demonstrating the exercise before). □