Problem 1

The answer is four.

Theorem. Four orderings are sometimes necessary.




Proof. In the diagram above, each of the four diagonal directions requires a different rectangle to be translated first.

QED



Theorem. Four orderings are sufficient.

We will require the following lemma.

Lemma. There exists a rectangle in the set such that no other rectangle lies in the quadrant above it or to the right of it.




Proof. Let's call this quadrant the northeast quadrant of the rectangle. We show that the relation "R2 lies in the northeast quadrant of R1" yields a partial ordering of the set of rectangles. Suppose we have a rectangle R2 in the northeast quadrant of R1. We have two cases. Either
  1. The bottom edge of R2 is higher than the top edge of R1, and the right edge of R2 is farther right than the left edge of R1.
  2. The left edge of R2 is farther right than the right edge of R1, and the top edge of R2 is higher than the bottom edge of R1.
Suppose the relation "R2 lies in the northeast quadrant of R1" produces a cyclic ordering. Then let R1, R2, ..., Rk be the shortest such cycle. Suppose WLOG that case 1 holds; that the top edge of Rk lies below the bottom edge of R1. Note that R1 cannot lie in the northeast quadrant of Rk-1, since this would give rise to a shorter cycle. Since Rk-1 must lie below Rk, Rk-1 must lie strictly to the right of R1 (that is, the left edge of Rk-1 lies farther right than the right edge of R1).

Again, Rk-1 is in the northeast quadrant of Rk-2. Note that Rk-1 cannot lie in the northeast quadrant of Rk-2, since this would give rise to a shorter cycle. Since Rk-2 must lie below Rk-1, Rk-2 must lie strictly to the right of Rk, and therefore strictly to the right of R1. We can continue this argument until we reach the point where R2 must lie below and to the right of R1, and we have a contradiction that R2 lies in the northeast quadrant of R1.

QED (lemma)

Suppose we are given a translation direction d. If d points in a northeasterly direction, we find the rectangle of the set which has no other rectangles in its northeast quadrant, and translate it to infinity. We then choose a rectangle of the remainder of the set with no other rectangles in its northeast quadrant, and translate it to infinity. The same ordering will work no matter which direction we choose in the northeast quadrant.

We therefore need only one ordering per quadrant, for a total of four.

QED



Problem 2

Perform induction on the number of line segments within a weakly simple polygon. Suppose that you form the convex hull of the given segments. Together with the segments which have one endpoint touching the hull, you get a weakly simple polygon. This polygon contains some number of segments which dont intersect anything. If you manage to attach one of these segments to the boundary of your polygon, you have reduced the number of purely interior segments, so by induction you can triangulate. I'm sure you can see that its not difficult to do this. The base case is also quite easy (one interior segment).

Problem 3

This is explained in section 5.7 of the book (Voronoi diagrams - Connection to convex hulls , p.182, 2nd edition)

Problem 4

Focus on one line, and wlog let it be vertical. There are n-1 intersections on it, so n-2 segments between intersection points. The two lines that form any two consecutive intersection points meet to form a triangle that has a base on our vertical line. So if each of these triangles is empty, we're done. Now look at how any two pairs of lines might interact. Lets say we have pair of lines A,B that form a triangle (T) to the right of the vertical line. If another pair of lines C,D has its triangle (T2) to the left, then the lines might extend to cross through T. They would just form a new triangle within T. So can still "charge" a triangle to the base of T. If C and D meet on the right side, we could have just one cross through T, which is ok, as above. Or, both could cross through T: case1: if they actually intersect within T, then we get 2 new triangles inside T. One of the new triangles will belong to the base of T, and the other to the base of T2. You can draw an example to see how to consistently assign the new triangles... meaning, in this case only one of A,B crosses through T2 so it is uniquely assigned one of the two newly formed triangles. Case2: if C and D dont intersect in T, then there is a new triangle in T (and outside of T2), and a new triangle in T2 (and outside of T). So for every triangle T that we start out with, we can go through all other pairs of adjacent lines and conclude that we will always get a new triangle inside T, that can be charged to the base of T. This gives us n-2 triangles.

For part (b), assume that the statement is true for n lines. When you add a new one, it cuts through n+1 faces. For any face F that is cut into two new ones, L and R, its not hard to show that the new contribution to the sum is increased only if the cut is very uneven. The difference is at most some linear amount in the size of the largest of the two new faces. This should be enough to show that you are still within the given bound, for the problem size of n+1.
A little more to get you started on a formal proof: let F have k edges on it. Then L+R = k+4. Also you can assume L<=R so L2+R2 is less than k2, when its more, and by how much.

Problem 5

This problem is fairly straightforward. If three points form a farthest-point Delaunay triangle, then their Voronoi cells must share a vertex. (This is even more clear if you consider that no farthest-point Voronoi cell can be bounded.) That vertex is equidistant to the three points of the triangle, each of which is farthest from the vertex. Therefore a circle through those three points contains the entire set.

The reverse is also clear. If an enclosing circle touches three points of the set, the center of that circle is on the Voronoi cells of those three points, and thus they form a Delaunay triangle.

For an algorithm, simply compute the farthest-point Delaunay triangulation. For each triangle (of which there are n), compute how large the circle determined by their three points is.