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

Exercise 2.1. Show that the use of the word 'convex' in convex hull is justified; that is, show that conv(S) is indeed a convex region.


Proof. Just proving that the intersection of any two convex hull is a convex hull is enough, which is not hard at all. However the fact that the characteristics are preserved when the intersection has been applied for infinite number of times is in a strict mathematical sense non-trivial though straightforward. □

Exercise 2.3. Let S be the four points {(0,0), (0,1), (1,0), (1,1)} in the plane. Show using Theorem 2.2 that conv(S) is the square with vertices at S.


Proof. The square can be represented by {(x,y) | 0 ≤x ≤ 1 and 0 ≤ y ≤ 1]}, so we need to prove that it is equal to conv(S), say they contain each other. The proof is not difficult and omitted. □

Exercise 2.4. For a point set S in the plane with at least four points, show that S can be partitioned into two sets A and B so that conv(A) intersects conv(B).

Proof. There are a few cases,
 - If three points are collinear, then the set can be divided into a line segment between the two points at the sides of the three collinear points and a line segment between the point in the middle and the remaining point and these two line segments intersect.
 - Otherwise no three points are collinear, so a triangle can be formed by any three of them, the the remaining point can either be
 -- inside the triangle, in which case the first set is the triangle and the second is the remaining point
 -- outside the triangle but within one of the interior angles of the triangle, in which case the first set is the line segment between the vertex the angle is around and the outside point and the second is the edge opposite the vertex.
 -- outside the triangle and not within any of the interior angles but within an angle opposite an internal, in which case the outside point and the edge opposite the point the internal angle is around can form a triangle which contains the point. □

Exercise 2.5. Show that conv(S) is the convex polygon with the smallest perimeter that contains S.


Proof. If there is another one that has smaller perimeter, suppose it's P'. As a convex polygon, it has to contain all the edges of conv(S). As it's a convex polygon other than conv(S) and by definition it contains conv(S) (Note: which means there are points in P' but not in conv(S)),  there must be at least one edge of conv(S) such that on the exterior side of conv(S)  there are points in P', and the intersection between the straight line the edge is on and P' should be able to replace the contour of P' on the side of the straight line exterior to conv(S) without disabling P' to meet the requirements, and as line segment is the shortest between two points, it contradicts P' having the smallest perimeter. □

Exercise 2.6. Show that conv(S) is the convex polygon with the smallest area that contains S.


Proof. Just need to prove that the intersection of two convex polygons is smaller in area than either of them. □

Exercise 2.7. Show that the rectangle of smallest area enclosing a point set S has at least one of its sides flush with (i.e., containing) an edge of conv(S).

Proof. It can be seen that it's true for the case of four vertices, since as the enclosing rectangle rotates with itself contacting the quadrilateral just at its four vertices its size either monotonously varies or passes through a maximum but never a minimum (this needs some effort). And to prove this statement of exercise, only proving that the enclosing rectangle of convex polygon is enough. Notice that if the none of the edges of the enclosing polygon flushes with the edge of the convex polygon, it touches the polygon also at its four vertices and we can easily apply the above result here and find that the rectangle can never reach a minimum in such circumstances. □