CS507: Computational Geometry
Instructor: Godfried Toussaint
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.
I'll do the infinite-order metric first. In this metric, two points p1 and p2 are distance max(|x1 - x2|, |y1 - y2|) apart. Suppose the diameter of the set is determined by a and b. Suppose WLOG that |xa - xb| > |ya - yb|. Then it follows that for no other pair of points c and d is |xc - xd| > |xa - xa|, 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 p1
and p2 are distance (|x1
- x2| + |y1 - y2|) apart.
If you play with the algebra, you get that this is equivalent
to max(|(x1 + y1) - (x2
+ y2)|, |(x1 - y1) - (x2
- y2)|). Then you can use the same algorithm
as above, finding the points (x+y)-min, (x+y)-max,
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:
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.
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.
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.