Assignments 3 - Solutions

(Solutions by Greg Aloupis)

Question 1:

Theorem. The Two-Coins algorithm computes the diameter of a convex unimodal polygon P.

Define the local maximum of vertex vi to be the longest diagonal that has vi as one of its vertices. By definition, the diameter of P is a local maximum for two of its vertices. Thus, it suffices to show that the Two-Coins algorithm does not miss any of local maxima of two vertices. We require the following lemma.

Lemma. Let (p,q) be the local maximum of vertex p and of q, and let p, r, s, q be on the chain in clockwise order. Then (r,s) is shorter than (r, q).

Proof. Since (p,s) < (p,q), the angle psq is less than angle sqp. Thus the larger angle psq + rsp > sqp - pqr. This implies that rsq > rqs, which implies that (r,s) < (r,q).

So suppose that (p,q) is missed the first time around. This means that the lead coin must be past q when the tail coin hits p. If we miss (p,q) when the tail coin gets to q, it means the lead coin must have passed p at some point. That means that for vertex between p and q, moving the lead past p further along this subchain increased the distance between the coins, violating the lemma.
QED

Question 2:

I'll do the infinite-order metric first. In this metric, two points p₁ and p₂ are distance max(|x₁ - x₂|, |y₁ - y₂|) apart. Suppose the diameter of the set is determined by a and b. Suppose WLOG that |x_a - x_b| > |y_a - y_b|. Then it follows that for no other pair of points c and d is |x_c - x_d| > |x_a - x_a|, since this would imply that c and d are farther apart than a and b.

Therefore it suffices to find the pair of points which differ the most in x-coordinate, and then those that differ in y-coordinate, and then choose the larger distance. Finding the pair which differ by the most is simply finding x-min and x-max, and y-min and y-max, which can be done in linear time.

Now for the first order metric. In this metric, two points p₁ and p₂ are distance (|x₁ - x₂| + |y₁ - y₂|) apart. If you play with the algebra, you get that this is equivalent to max(|(x₁ + y₁) - (x₂ + y₂)|, |(x₁ - y₁) - (x₂ - y₂)|). Then you can use the same algorithm as above, finding the points (x+y)-min, (x+y)-max, (x-y)-min, (x-y)-max.

Question 3:

Part (a)

We can reduce Convex Hull to Triangulation. Let Algorithm T be some algorithm to triangulate a set of n points in the plane. I can find the convex hull of any set as follows:

1. Triangulate the set with Algorithm T.
2. Find x-min and x-max.
3. Travel along the triangulation from x-min to x-max by always traversing the lowest edge available which proceeds to the right. Mark all vertices we traverse.
4. Travel along the triangulation from x-max to x-min by always traversing the highest edge available which proceeds to the left. Mark all vertices we traverse.

We know that the the convex hull is contained in the triangulation. If it weren't, then we could always add a pocket lid while keeping the graph planar, which contradicts the fact that the triangulation is the maximal complete geometric (meaning all edges are line segments) graph on the point set. Note that in Step 3, we find the lower convex hull by ensuring that the exterior of the convex hull is always just below the edge on which we traverse. Similarly, in Step 4, we find the upper convex hull. Since at all times the exterior of the convex hull is just above or below the edge we are traversing -- and we never backtrack on an edge -- it follows that we have traced the entire convex hull.

For the time complexity, Step 2 takes linear time. Steps 3 and 4 are repeated occurrences of selecting the highest or lowest edges from a list of edges at each vertex. Since each edge is adjacent to two vertices, we are guaranteed not to examine any edge more than twice. Since the number of edges in the triangulation is no more than 3n, Steps 3 and 4 are linear. Since Convex Hull has a lower bound on the time complexity of Omega(n log n), so too must Algorithm T.

Part (b)

The conjecture is true.

This time I'll reduce Sorting to our modified problem. Suppose you have a set A which you want to sort. Then I do the following.

• For each element a_i in A, I add the point (a_i, i) to my set S.
• Consider the polygonal chain (a₁, 1), (a₂, 2), ..., (a_n, n). Since it's sorted by y-coordinate, I can run three-coins on it to get a triangulation.
• I have a triangulation of S, so I run an algorithm which takes this triangulation and produces a sorted list of the x-coordinates of the points in S.

Note that Steps 1 and 2 are linear time steps. We end up with a sorting of the set A, so Step 3 must take Omega(n log n) time.

Question 4:

Suppose our polygon is not weakly externally visible, such that a and b form the lid of a pocket in which some vertices cannot see out to infinity. Walking along the chain from a to b, let pq be the last edge on which no point except the endpoints can see to infinity. I have to prove that such an edge exists.

Lemma. In a non-WEV polygon, there is some edge which cannot see to infinity, except possibly at only one of its endpoints.

Proof. Suppose that some point p cannot see to the pocket lid ab. We now show that one of the edges adjacent to p cannot see the pocket lid (except from the other endpoint). Suppose for the sake of contradiction that the two adjacent edges, op and pq, can see the lid ab. Let o's be some line segment from a point o' in the interior of op to a point s on ab which does not intersect the polygon (except at o'). This is possible by our assumption that some interior point of op can see ab. Likewise, let q't be some line segment from a point q' in the interior of pq to a point t on ab which does not intersect the polygon (except at q').

If o's and q't do not intersect, then it follows that no point in the polygon enters the quadrilateral so'q't, and thus also the pentagon so'pq't. It is clear that the vertices at o' and q' are convex, and since s and t are on the convex hull edge ab, they are also convex. Thus p can see the edge st, and through it to infinity.

If o's and q't do intersect, then label their intersection point as z. Then it follows from above that no point in the polygon enters the convex quadrilateral zo'pq', and also the triangle zst. Therefore p can see z, through the opposite angle into the triangle, and out to infinity.
QED (lemma)

Just as a review, suppose our polygon is not weakly externally visible, such that a and b form the lid of a pocket in which some vertices cannot see out to infinity. Walking along the chain from a to b, let pq be the last edge on which no point except the endpoints can see to infinity, and further let p be the endpoint which cannot see the lid ab. We assume that the order of the vertices clockwise is a, p, q, b. (If this is not the case, then we can switch the labelling of a and b and/or the orientation of the polygon.)

We now run three-coins algorithm so that a precedes b in the order of the vertices being examined. At some point the lead coin will get to p. Since the three-coins algorithm never allows a left-turn to stay in the data structure, the current convex-hull chain candidate has all right-turns. Thus a to p is all right turns.

We assume for now that there is no loop between a and p and thus from a to p must be a simple chain in the candidate convex-hull chain. Note that a to p to q is a right turn -- since pq must point into the candidate convex-hull chain. This is because q can see to infinity, but p cannot, so the ray pq must be obstructed by what has come before it. Thus p is deemed to be a right turn. Further, q can see to infinity, although no point inside the edge pq can. Therefore the ray at which q sees to infinity must be a right turn from pq so that all external points on pq are obstructed from view. (Recall that as we traverse a polygon clockwise the exterior of a polygon lies to the left of every edge.) Since no points of the polygon can again cross this ray, and thus the ray through pq, q will always be a right turn. Since q will not be popped from the stack, p, which precedes it, cannot be popped from the stack. Since p is not on the convex hull, the three-coins algorithm fails.

If there is a loop inside the pocket from a to b when we reach p, then consider when the three-coins algorithm reaches q as the lead coin. The loop is still there, yet since q can see to infinity, the only possible way to backtrack to break the loop is to go in the clockwise direction, under the edge pq. As we travel back this way, consider the rightmost point the path from q back to the loop. This is necessarily a right turn, and thus cannot be popped. Therefore the loop, which precedes it in the candidate convex-hull chain, cannot be popped.
QED

Perouz Taslakian
Office Hours: Wednesdays 11:00am - 1:00pm
Office : MC 232
Tel: (514) 398-7071 ext. #0345
http://cgm.cs.mcgill.ca/~perouz