chap35.htm

介绍算法的书籍

<h2>Graham's scan</h2><P>
<a name="09ef_1c41"><a name="09ef_1c42"><I><B>Graham's</I></B> <I><B>scan</I></B> solves the convex-hull problem by maintaining a stack <I>S</I> of candidate points. Each point of the input set <I>Q</I> is pushed once onto the stack, and the points that are not vertices of CH(<I>Q</I>) are eventually popped from the stack. When the algorithm terminates, stack <I>S</I> contains exactly the vertices of CH(<I>Q</I>), in counterclockwise order of their appearance on the boundary.<P>
<img src="900_a.gif"><P>
<h4><a name="09ef_1c48">Figure 35.7 The execution of <FONT FACE="Courier New" SIZE=2>GRAHAM-SCAN</FONT> on the set Q of Figure 35.6. The current convex hull contained in stack S is shown in gray at each step. (a) The ordered polar angles of <img src="../images/lftwdchv.gif">p<SUB>1</SUB>,p<SUB>2</SUB>, . . . , p<SUB>12</SUB><img src="../images/wdrtchv.gif"> relative to p<SUB>0</SUB> and the initial stack S containing p<SUB>0</SUB>, p<SUB>1</SUB>, and p<SUB>2</SUB>. (b)-(k) Stack S after each iteration of the for loop of lines 7-10. Dashed lines show nonleft turns, which cause points to be popped from the stack. In part (h), for example, the right turn at angle <img src="../images/angle.gif">p<SUB>7</SUB>p<SUB>8</SUB>p<SUB>9</SUB> causes p<SUB>8</SUB> to be popped, and then the right turn at angle <img src="../images/angle.gif">p<SUB>6</SUB>p<SUB>7</SUB>p<SUB>9</SUB> causes p<SUB>7</SUB> to be popped. (l) The convex hull returned by the procedure, which matches that of Figure 35.6.<a name="09ef_1c48"></sub></sup></h4><P>
<img src="901_a.gif"><P>
<a name="09ef_1c43"><a name="09ef_1c44">The procedure <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT> takes as input a set <I>Q</I> of points, where |<I>Q| </I><img src="../images/gteq.gif"> 3. It calls the functions <FONT FACE="Courier New" SIZE=2>TOP</FONT>(<I>S</I>), which returns the point on top of stack <I>S</I> without changing <I>S</I>, and <FONT FACE="Courier New" SIZE=2>NEXT</FONT>-<FONT FACE="Courier New" SIZE=2>TO</FONT>-<FONT FACE="Courier New" SIZE=2>TOP</FONT>(<I>S</I>), which returns the point one entry below the top of stack <I>S</I> without changing <I>S</I>. As we shall prove in a moment, the stack <I>S</I> returned by <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT> contains, from bottom to top, exactly the vertices of CH(<I>Q</I>) in counterclockwise order.<P>
<pre><a name="09ef_1c45">GRAHAM-SCAN<I>(Q)</I></sub></sup></pre><P>
<pre>1  let <I>p</I><SUB>0</SUB> be the point in <I>Q</I> with the minimum <I>y</I>-coordinate,</sub></sup></pre><P>
<pre>or the leftmost such point in case of a tie</sub></sup></pre><P>
<pre>2  let <img src="../images/lftwdchv.gif"><I>p</I><SUB>1</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p<SUB>m</I></SUB><img src="../images/wdrtchv.gif"> be the remaining points in <I>Q</I>,</sub></sup></pre><P>
<pre>sorted by polar angle in counterclockwise order around <I>p</I><SUB>0</sub></sup></pre><P>
<pre>(if more than point has the same angle, remove all but</sub></sup></pre><P>
<pre>the one that is farthest from <I>p</I><SUB>0</SUB>)</sub></sup></pre><P>
<pre>3  <I>top</I>[<I>S</I>]<img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>4  PUSH(<I>p</I><SUB>0</SUB>,<I>S</I>)</sub></sup></pre><P>
<pre>5  PUSH(<I>p</I><SUB>1</SUB>,<I>S</I>)</sub></sup></pre><P>
<pre>6  PUSH(<I>p</I><SUB>2</SUB>,<I>S</I>)</sub></sup></pre><P>
<pre>7  <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 3 <B>to</B> <I>m</I></sub></sup></pre><P>
<pre>8        <B>do while</B> the angle formed by points NEXT-TO-TOP(<I>S</I>),</sub></sup></pre><P>
<pre>TOP(<I>S</I>), and <I>p<SUB>i</I></SUB> makes a nonleft turn</sub></sup></pre><P>
<pre>9               <B>do</B> POP(<I>S</I>)</sub></sup></pre><P>
<pre>10           PUSH(<I>S,p<SUB>i</I></SUB>)</sub></sup></pre><P>
<pre>11  <B>return</B> <I>S</I></sub></sup></pre><P>
Figure 35.7 illustrates the progress of <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT>. Line 1 chooses point <I>p</I><SUB>0</SUB> as the point with the lowest <I>y</I>-coordinate, picking the leftmost such point in case of a tie. Since there is no point in <I>Q</I> that is below <I>p</I><SUB>0</SUB> and any other points with the same <I>y</I>-coordinate are to its right, <I>p</I><SUB>0</SUB> is a vertex of CH(<I>Q</I>). Line 2 sorts the remaining points of <I>Q</I> by polar angle relative to <I>p</I><SUB>0</SUB>, using the same method--comparing cross products--as in Exercise 35.1-2. If two or more points have the same polar angle relative to <I>p</I><SUB>0</SUB>, all but the farthest such point are convex combinations of <I>p</I><SUB>0</SUB> and the farthest point, and so we remove them entirely from consideration. We let <I>m</I> denote the number of points other than <I>p</I><SUB>0</SUB> that remain. The polar angle, measured in radians, of each point in <I>Q</I> relative to <I>p</I><SUB>0</SUB> is in the half-open interval [0, <img src="../images/piuc.gif">/2). Since polar angles increase in a counterclockwise fashion, the points are sorted in counterclockwise order relative to <I>p</I><SUB>0</SUB>. We designate this sorted sequence of points by <img src="../images/lftwdchv.gif"><I>p</I><SUB>1</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p<SUB>m </SUB></I><img src="../images/wdrtchv.gif"><I>.</I> Note that points <I>p</I><SUB>1</SUB> and <I>p<SUB>m </I></SUB>are vertices of CH(<I>Q</I>) (see Exercise 35.3-1). Figure 35.7(a) shows the points of Figure 35.6, with the ordered polar angles of <img src="../images/lftwdchv.gif"><I>p</I><SUB>1</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p</I><SUB>12</SUB><img src="../images/wdrtchv.gif"> relative to <I>p</I><SUB>0</SUB>.<P>
The remainder of the procedure uses the stack <I>S</I> Lines 3-6 initialize the stack to contain, from bottom to top, the first three points <I>p</I><SUB>0</SUB>, <I>p</I><SUB>1</SUB>, and <I>p</I><SUB>2</SUB>. Figure 35.7(a) shows the initial stack <I>S</I>. The <B>for</B> loop of lines 7-10 iterates once for each point in the subsequent <img src="../images/lftwdchv.gif"><I>p<SUB>3</SUB>, p<SUB>4</SUB>, . . . ,p<SUB>m</SUB>)</I> The intent is that after processing point <I>p<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB>, stack <I>S</I> contains, from bottom to top, the vertices of CH({<I>p</I><SUB><FONT FACE="Courier New" SIZE=2>0</FONT></SUB>,<I>p</I><SUB><FONT FACE="Courier New" SIZE=2>1</FONT></SUB>, . . . ,<I>p<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB>}) in counterclockwise order. The <B>while</B> loop of lines 8-9 removes points from the stack if they are found not to be vertices of the convex hull. When we traverse the convex hull counterclockwise, we should make a left turn at each vertex. Thus, each time the <B>while</B> loop finds a vertex at which we make a nonleft turn, the vertex is popped from the stack. (By checking for a nonleft turn, rather than just a right turn, this test precludes the possibility of a straight angle at a vertex of the resulting convex hull. This is just what we want, since every vertex of a convex polygon must not be a convex combination of other vertices of the polygon.) After we pop all the vertices that have nonleft turns when heading toward point <I>p<SUB><FONT FACE="Courier New" SIZE=2>i</SUB>,</I></FONT> we push <I>p<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB> onto the stack. Figures 35.7(b)-(k) show the state of the stack <I>S</I> after each iteration of the <B>for</B> loop. Finally, GRAHAM-SCAN returns the stack <I>S</I> in line 11. Figure 35.7(1) shows the corresponding convex hull.<P>
The following theorem formally proves the correctness of <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT>.<P>
<a name="09ef_1c49">Theorem 35.2<a name="09ef_1c49"><P>
If <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT> is run on a set<I> Q</I> of points, where |<I>Q| <img src="../images/gteq.gif"> 3, then a point of </I>Q<I> is on the stack</I> S<I> at termination if and only if it is a vertex of CH(</I>Q<I>).</I><P>
<I><B>Proof     </I></B>As noted above, a vertex that is a convex combination of <I>p</I><SUB>0</SUB> and some other vertex in <I>Q</I> is not a vertex of CH(<I>Q</I>). Such a vertex is not included in the sequence <img src="../images/lftwdchv.gif"><I>p</I><SUB>l</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p </I><SUB>m</SUB><img src="../images/wdrtchv.gif">, and so it can never appear on stack <I>S</I>.<P>
The crux of the proof lies in the two situations shown in Figure 35.8. Part (a) deals with nonleft turns, and part (b) deals with left turns.<P>
We first show that each point popped from stack <I>S</I> is not a vertex of CH(<I>Q</I>). Suppose that point <I>p<SUB>j</I></SUB> is popped from the stack because angle <img src="../images/angle.gif"><I>p<SUB>k</SUB>p<SUB>j</SUB>p<SUB>i</I></SUB> makes a nonleft turn, as shown in Figure 35.8(a). Because we scan the points in order of increasing polar angle relative to point p<SUB>0</SUB>, there is a triangle <img src="903_a.gif"> with point <I>p<SUB>j</I></SUB> either in the interior of the triangle or<B> </B>on line segment <img src="903_b.gif">. In either case, point <I>p<SUB>j</I></SUB> cannot be a vertex of CH(<I>Q</I>).<P>
We now show that each point on stack <I>S</I> is a vertex of CH(<I>Q</I>) at termination. We start by proving the following claim: <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT> maintains the invariant that the points on stack <I>S</I> always form the vertices of a convex polygon in counterclockwise order.<P>
The claim holds immediately after the execution of line 6, since points <I>p</I><SUB>0</SUB>, <I>p</I><SUB>1</SUB>, and <I>p<SUB>2</I></SUB> form a convex polygon. Now we examine how stack <I>S</I> changes during the course of <I>G<FONT FACE="Courier New" SIZE=2>RAHAM</I></FONT>-<I>S<FONT FACE="Courier New" SIZE=2>CAN</I></FONT>. Points are either popped or pushed. In the former case, we rely on a simply geometrical property: if a vertex is removed from a convex polygon, the resulting polygon is convex. Thus, popping a point from stack <I>S</I> preserves the invariant.<P>
<img src="904_a.gif"><P>
<h4><a name="09ef_1c4a">Figure 35.8 The two basic situations in the proof of correctness of <FONT FACE="Courier New" SIZE=2>GRAHAM<FONT FACE="Times New Roman" SIZE=2>- <FONT FACE="Courier New" SIZE=2>SCAN<FONT FACE="Times New Roman" SIZE=2>.</FONT></FONT></FONT></FONT> (a) Showing that a point popped from the stack in <FONT FACE="Courier New" SIZE=2>GRAHAM<FONT FACE="Times New Roman" SIZE=2>-</FONT>SCAN<FONT FACE="Times New Roman" SIZE=2> </FONT></FONT>is not a vertex of CH(Q). If point p<SUB>j</SUB><FONT FACE="Times New Roman" SIZE=2></FONT> is popped from the stack because angle <img src="../images/angle.gif">p<SUB>k</SUB><FONT FACE="Times New Roman" SIZE=2>p<SUB>j</SUB><FONT FACE="Times New Roman" SIZE=2>p<SUB>i</SUB><FONT FACE="Times New Roman" SIZE=2> </FONT></FONT></FONT>makes a nonleft turn, then the shaded triangle <img src="904_b.gif"> contains point p<SUB>j</SUB><FONT FACE="Times New Roman" SIZE=2>. </FONT>Point p<SUB>j</SUB><FONT FACE="Times New Roman" SIZE=2> </FONT>is therefore not a vertex of CH(Q). (b) If point p<SUB>i</SUB><FONT FACE="Times New Roman" SIZE=2> </FONT>is pushed onto the stack, then there must be a left turn at angle <img src="../images/angle.gif">p<SUB>k</SUB>p<SUB>j</SUB><FONT FACE="Times New Roman" SIZE=2>p<SUB>i</SUB><FONT FACE="Times New Roman" SIZE=2>. </FONT></FONT>Because p<SUB>i</SUB><FONT FACE="Times New Roman" SIZE=2> </FONT>follows p<SUB>j</SUB> in the polar-angle ordering of points and because of how p<SUB>0</SUB><FONT FACE="Times New Roman" SIZE=2> </FONT>was chosen, p<SUB>i</SUB><FONT FACE="Times New Roman" SIZE=2> </FONT>must be in the shaded region. If the points on the stack form a convex polygon before the push, then they must form a convex polygon afterward.<a name="09ef_1c4a"></sub></sup></h4><P>
Before we consider the case in which a point is pushed onto the stack, let us examine another geometrical property, illustrated in Figures 35.9(a) and (b). Let <I>P</I> be a convex polygon, and choose any side <img src="904_c.gif"> of <I>P</I>. Consider the region bounded by <img src="904_d.gif"> and the extensions of the two adjacent sides. (Depending on the relative angles of the adjacent sides, the region may be either bounded, like the shaded region in part (a), or unbounded, like the shaded region in part (b).) If we add any point <I>p<SUB>s</I></SUB> in this region to <I>P</I> as a new vertex, with the sides<img src="904_e.gif"><I><SUB> </I></SUB> replacing side <img src="904_f.gif">, the resulting polygon is convex.<P>
Now consider a point <I>pi</I> that is pushed onto <I>S</I>. Referring back to Figure 35.8(b), let <I>p<SUB>j</I></SUB> be the vertex on the top of <I>S</I> just prior to pushing <I>pi,</I> and let <I>p<SUB>k</I></SUB> be the predecessor of <I>p<SUB>j</I></SUB> on <I>S</I>. We claim that <I>p<SUB>i</I></SUB> must fall within the shaded region of Figure 35.8(b), which corresponds directly to the shaded regions of Figure 35.9. Because the angle <img src="../images/angle.gif">p<SUB>k</SUB>p<SUB>j</SUB>p<SUB>i</SUB> makes a left turn, <I>p<SUB>i</I></SUB> must be on the shaded side of the extension of <img src="904_g.gif">. Because <I>p<SUB>i</I></SUB> follows <I>p<SUB>j</I></SUB> in the polar-angle ordering, it must be on the shaded side of <img src="904_h.gif">. Moreover, because of how we chose <I>p</I><SUB>0</SUB>, point <I>p<SUB>i</SUB> </I>must be on the shaded side of the extension of <img src="904_i.gif">. Thus<I>, p<SUB>i</I></SUB> is in the shaded region, and therefore after <I>p<SUB>i</I></SUB> has been pushed onto stack <I>S</I>, the points on <I>S</I> form a convex polygon. This completes the proof of the claim.<P>
At the end of <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT>, therefore, the points of <I>Q</I> that are on stack <I>S</I> form the vertices of a convex polygon. We have shown that all points not on <I>S</I> are not vertices of CH(<I>Q</I>) or, equivalently, that all vertices of CH(<I>Q</I>) are on <I>S</I>. Since <I>S</I> contains only vertices from <I>Q</I> and its points form a convex polygon, they must form CH(<I>Q</I>).  <P>
<img src="905_a.gif"><P>
<h4><a name="09ef_1c4b">Figure 35.9 Adding a point in the shaded region to a convex polygon P yields another convex polygon. The shaded region is bounded by a side of <img src="905_b.gif"> and the extensions of the two adjacent sides. (a) The shaded region is bounded. (b) The shaded region is unbounded.<a name="09ef_1c4b"></sub></sup></h4><P>
We now show that the running time of <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT> is <I>O</I>(<I>n</I> lg <I>n</I>), where <I>n</I> = |<I>Q</I>|. Line 1 takes<img src="../images/bound.gif">(<I>n</I>) time. Line 2 takes <I>O</I>(<I>n</I> lg <I>n</I>) time, using merge sort or heapsort to sort the polar angles and the cross-product method of Section 35.1 to compare angles. (Removing all but the farthest point with the same polar angle can be done in a total of <I>O</I>(<I>n</I>) time.) Lines 3-6 take <I>O</I>(1) time. Because <I>m</I> <img src="../images/lteq12.gif"> <I>n</I> - 1, the <B>for</B> loop of lines 7-10 is executed at most <I>n</I> - 3 times. Since <FONT FACE="Courier New" SIZE=2>PUSH</FONT> takes <I>O</I>(1) time, each iteration takes <I>O</I>(1) time exclusive of the time spent in the <B>while</B> loop of lines 8-9, and thus overall the <B>for</B> loop takes <I>O</I>(<I>n</I>) time exclusive of the nested <B>while</B> loop.<P>
<a name="09ef_1c46"><a name="09ef_1c47">We use the aggregate method of amortized analysis to show that the <B>while</B> loop takes <I>O</I>(<I>n</I>) time overall. For <I>i</I> = O, 1, . . . , <I>m</I>, each point <I>p<SUB>i</I></SUB> is pushed onto stack <I>S</I> exactly once. As in the analysis of the <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> procedure of Section 18.1, we observe that there is at most one <FONT FACE="Courier New" SIZE=2>POP</FONT> operation for each <FONT FACE="Courier New" SIZE=2>PUSH</FONT> operation. At least three points--<I>p</I><SUB>0</SUB>, <I>p</I><SUB>1</SUB>, and <I>p<SUB>m</I></SUB>--are never popped from the stack, so that in fact at most <I>m</I> - 2 <FONT FACE="Courier New" SIZE=2>POP</FONT> operations are performed in total. Each iteration of the <B>while</B> loop performs one <FONT FACE="Courier New" SIZE=2>POP</FONT>, and so there are at most <I>m</I> - 2 iterations of the <B>while</B> loop altogether. Since the test in line 8 takes <I>O</I>(1) time, each call of <FONT FACE="Courier New" SIZE=2>POP</FONT> takes <I>O</I>(1) time, and <I>m</I> <img src="../images/lteq12.gif"> <I>n</I> - 1, the total time taken by the <B>while</B> loop is <I>O</I>(<I>n</I>)<I>. </I>Thus, the running time of <FONT FACE="Courier New" SIZE=2>GRAHAM</FONT>-<FONT FACE="Courier New" SIZE=2>SCAN</FONT> is <I>O</I>(<I>n</I> lg <I>n</I>).<P>
<P>







<h2>Jarvis's march</h2><P>
<a name="09f0_1c48"><a name="09f0_1c49"><a name="09f0_1c4a"><I><B>Jarvis's march</I></B> computes the convex hull of a set Q of points by a technique<B> </B>known as <I><B>package wrapping</I></B> (or <I><B>gift wrapping</I></B>). The algorithm runs in time <I>O</I>(<I>nh</I>), where <I>h</I> is the number of vertices of CH(<I>Q</I>). When <I>h</I> is <I>o</I>(lg<I> n</I>), Jarvis's march is asymptotically faster than Graham's scan.<P>
<img src="906_a.gif"><P>
<h4><a name="09f0_1c4c">Figure 35.10 The operation of Jarvis's march. The first vertex chosen is the lowest point p<SUB>0</SUB>.  The next vertex, p<SUB>1</SUB>, has the least polar angle of any point with respect to p<SUB>0</SUB>. Then, p<SUB>2</SUB> has the least polar angle with respect to p<SUB>1</SUB>. The right chain goes as high as the highest point p<SUB>3</SUB>. Then, the left chain is constructed by finding least polar angles with respect to the negative x-axis.<a name="09f0_1c4c"></sub></sup></h4><P>
Intuitively, Jarvis's march simulates wrapping a taut piece of paper around the set <I>Q</I>. We start by taping the end of the paper to the lowest point in the set, that is, to the same point <I>p</I><SUB>0</SUB> with which we start Graham's scan. This point is a vertex of the convex hull. We pull the paper to the right to make it taut, and then we pull it higher until it touches a point. This point must also be a vertex of the convex hull. Keeping the paper taut, we continue in this way around the set of vertices until we come back to our original point <I>p</I><SUB>0</SUB>.<P>
<a name="09f0_1c4b">More formally, Jarvis's march builds a sequence <I>H</I> = <img src="../images/lftwdchv.gif"><I>p</I><SUB>0</SUB>, <I>p</I><SUB>1</SUB>, . . . , <I>p<SUB>h</I>-1</SUB><img src="../images/wdrtchv.gif"> of the vertices of CH(<I>Q</I>). We start with <I>p</I><SUB>0</SUB>. As Figure 35.10 shows, the next convex hull vertex <I>p</I><SUB>1</SUB> has the least polar angle with respect to <I>p</I><SUB>0</SUB>. (In case of ties, we choose the point farthest from <I>p</I><SUB>0</SUB>.) Similarly, <I>p</I><SUB>2</SUB> has the least polar angle with respect to <I>p</I><SUB>l</SUB>, and so on. When we reach the highest vertex, say <I>p<SUB>k</I></SUB> (breaking ties by choosing the farthest such vertex), we have constructed, as Figure 35.10 shows, the <I><B>right chain</I></B> of CH(<I>Q</I>). To construct the <I><B>left chain</