Perouz's Homepage - COMP507

CS507: Computational Geometry

McGill University

Assignments 4 - Solutions

(Solutions by Greg Aloupis)

Question 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 "R₂ lies in the northeast quadrant of R₁" yields a partial ordering of the set of rectangles. Suppose we have a rectangle R₂ in the northeast quadrant of R₁. We have two cases. Either :

The bottom edge of R₂ is higher than the top edge of R₁, and the right edge of R₂ is farther right than the left edge of R₁.
The left edge of R₂ is farther right than the right edge of R₁, and the top edge of R₂ is higher than the bottom edge of R₁.
Suppose the relation "R₂ lies in the northeast quadrant of R₁" produces a cyclic ordering. Then let R₁, R₂, ..., R_k be the shortest such cycle. Suppose WLOG that case 1 holds; that the top edge of R_k lies below the bottom edge of R₁. Note that R₁ cannot lie in the northeast quadrant of R_k-1, since this would give rise to a shorter cycle. Since R_k-1 must lie below R_k, R_k-1 must lie strictly to the right of R₁ (that is, the left edge of R_k-1 lies farther right than the right edge of R₁).

Again, R_k-1 is in the northeast quadrant of R_k-2. Note that R_k-1 cannot lie in the northeast quadrant of R_k-2, since this would give rise to a shorter cycle. Since R_k-2 must lie below R_k-1, R_k-2 must lie strictly to the right of R_k, and therefore strictly to the right of R₁. We can continue this argument until we reach the point where R₂ must lie below and to the right of R₁, and we have a contradiction that R₂ lies in the northeast quadrant of R₁.
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

Question 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 don't 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).

Question 3:

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

Question 4:

a) 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 T₂ 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:

case 1: 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 T₂. 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 T₂ so it is uniquely assigned one of the two newly formed triangles.

case 2: if C and D dont intersect in T, then there is a new triangle in T (and outside of T₂), and a new triangle in T₂ (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.

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 L₂+R₂ is less than k₂, when its more, and by how much.

Question 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.