The objective of this problem is to investigate one approach for an O(m + n) tim

Question

The objective of this problem is to investigate one approach for an O(m + n) time algorithm to determine whether one convex polygon P lies inside of another convex polygon Q. Here m and n denote the number of vertices of P and Q, respectively. There are other algorithms for doing this (for example, the sweepline approach to find the intersection of two convex polygons), but here I would like you to consider this particular approach. Only PSEUDOCODE! You should present the following: the algorithm, a justification of its correctness, and a derivation of its running time

(a) Given the leftmost vertex v1 of Q, show how to use orientation tests to compute the counterclockwise point of tangency of P relative to v1, denoted t1. (More formally, P lies on and to the left of the directed line v1t1. Such a line is called a supporting line for P. See Figure 3.) Show that your method runs in O(m) time.

(b) Assuming that the CCW tangent point ti?1has already been computed for vertex vi?1 of Q, show how to compute the tangent point ti for the next vertex vi in CCW order about Q.

(c) Prove that as the tangent points are being computed, it is possible to determine whether P is not contained in Q.

(d) Assuming that P is contained within Q, show that all of these tangent points can be computed in O(m + n) time.

You may design your algorithms in (a) and (b) so that they terminate if it is discovered that P is not contained in Q.

Explanation / Answer

a)
Let q_0 be a point on the boundary of polygon Q.
Initialize q = q_0.

let q.pred be the preceeding in CCW order and q.next be the succeeding vertex of polygon Q.

badFlag = 0;
while
!(orient( vi-1 q q.next ) = left and orient( vi-1 q q.pred ) = left),
q = q.next
if q = q0
break, badFlag = 1, report "no tangent point"
fi
end
if badFlag == 0
return t1 = q
end

This does a constant time operation for each vertex in P, so it is O(m).

b)
vi = vi-1.next
q = ti-1 % notice, not ti-1.next

while
!(orient( vi q q.next ) = left and orient( vi q q.pred ) = left),
q = q.next
if q = ti-1
break, badFlag = 1, report "no tangent point"
fi
end
if badFlag == 0
return ti = q
end

(c)
So how can we tell if some point of P is outside Q? If a point in P is outside of Q (lets call this point t), then for some vertex vi, it must be the case that:

[ vi, vi+1, t ] is a right turn.

If there does not exist such a t, then all points in P lie to the left of edges in the convex hull of Q, so P must lie entirely in Q.

Furthermore, the only vertex t we have to check is the one returned by the answer in part (b). Since that vertex t is the lower tangent with respect to vi, then if [vi, vi+1, t ] is a left turn, all other points in P would also be a left turn. So we can do this single, constant time check at the end of each iteration of step (b).


(d)
Alg:

Run bit from part (a) to get a starting lower tangent. == O(m) time.

Iterate the step in part (b) to repeatedly find the next lower tangent.

This computation is a little harder to analyse its time. Clearly, we do the process in step (b) n times (once for each vertex in Q).
But how many times does the inner while loop execute? We need to consider the total running time over all updates --- the inner loop condition is checked at least once each time (b) is called, and once each time q is updated to q.next. Since the tangent line goes around P exactly once, q is updated exactly m times. So this is a
total number of operations of O(m + n).

So overall algorithm is O(m) + O(m+n) = O(m+n).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.