chap35.htm

介绍算法的书籍

The call <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECT</FONT>(<I>S</I>) returns <FONT FACE="Courier New" SIZE=2>TRUE<FONT FACE="Times New Roman" SIZE=2> </FONT></FONT>if and only if there is an intersection among the segments in <I>S.</I><P>
<I><B>Proof     </I></B>The procedure can be incorrect only by returning <FONT FACE="Courier New" SIZE=2>TRUE</FONT> when no intersection exists or by returning <FONT FACE="Courier New" SIZE=2>FALSE</FONT> when there is at least one intersection. The former case cannot occur, because <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-I<FONT FACE="Courier New" SIZE=2>NTERSECT </FONT>returns <FONT FACE="Courier New" SIZE=2>TRUE</FONT> only if it finds an intersection between two of the input segments.<P>
To show that the latter case cannot occur, let us suppose for the sake of contradiction that there is at least one intersection, yet <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECT</FONT> returns<FONT FACE="Courier New" SIZE=2> FALSE. </FONT>Let <I>p</I> be the leftmost intersection point, breaking ties by choosing the one with the lowest <I>y</I>-coordinate, and let <I>a </I>and<I> b </I>be the segments that intersect at <I>p.</I> Since no intersections occur to the left of <I>p,</I> the order given by <I>T</I> is correct at all points to the left of <I>p. </I>Because no three segments intersect at the same point, there exists a sweep line <I>z </I>at which <I>a</I> and <I>b</I> become consecutive in the total order.<SUP><FONT FACE="Times New Roman" SIZE=1>2</FONT></SUP> Moreover, <I>z</I> is to the left of <I>p</I> or goes through <I>p.</I> There exists a segment endpoint <I>q</I> on sweep line <I>z</I> that is the event point at which <I>a</I> and <I>b</I> become consecutive in the total order. If <I>p</I> is on sweep line <I>z</I>, then <I>q = p</I>. If <I>p</I> is not on sweep line <I>z,</I> then <I>q</I> is to the left of <I>p.</I> In either case, the order given by <I>T</I> is correct just before <I>q</I> is processed. (Here we rely on <I>p</I> being the lowest of the leftmost intersection points. Because of the lexicographical order in which event points are processed, even if <I>p</I> is on sweep line <I>z</I> and there is another intersection point <I>p</I>' on <I>z</I>, event point <I>q = p</I> is processed before the other intersection <I>p</I>' can interfere with the total order <I>T.</I>) There are only two possibilities for the action taken at event point <I>q:</I><P>
<SUP><FONT FACE="Times" SIZE=1>2</SUP><FONT FACE="Times" SIZE=2>If we allow three segments to intersect at the same point, there may be an intervening segment <I>c</I> that intersects both <I>a</I> and <I>b</I> at point <I>p</I>. That is, we may have <I>a</I> &lt;<I><SUB><FONT FACE="Times" SIZE=1>w</SUB> c</I><FONT FACE="Times" SIZE=2> and <I>c</I> &lt;<I><SUB><FONT FACE="Times" SIZE=1>w</SUB> b</I><FONT FACE="Times" SIZE=2> for all sweep lines <I>w</I> to the left of <I>p</I> for which <I>a</I> &lt;<I><SUB><FONT FACE="Times" SIZE=1>w</SUB> b</I><FONT FACE="Times" SIZE=2>.</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT><P>
1.     Either <I>a</I> or <I>b</I> is inserted into <I>T</I>, and the other segment is above or below it in the total order. Lines 4-7 detect this case.<P>
2.     Segments <I>a</I> and <I>b</I> are already in <I>T</I>, and a segment between them in the total order is deleted, making <I>a</I> and <I>b</I> become consecutive. Lines 8-11 detect this case.<P>
In either case, the intersection <I>p</I> is found, contradicting the assumption that the procedure returns <FONT FACE="Courier New" SIZE=2>FALSE</FONT>.      <P>
<P>







<h2>Running time</h2><P>
If there are <I>n</I> segments in set <I>S</I>, then <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECT</FONT> runs in time <I>O(n </I>lg <I>n</I>). Line 1 takes <I>O</I>(1) time. Line 2 takes <I>O(n </I>lg <I>n</I>) time, using merge sort or heapsort. Since there are 2<I>n</I> event points, the <B>for </B>loop of lines 3-11 iterates at most 2<I>n</I> times. Each iteration takes <I>0(</I>lg<I> n</I>) time, since each red-black-tree operation takes <I>O</I>(lg <I>n</I>) time and, using the method of Section 35.1, each intersection test takes <I>O</I>(1) time. The total time is thus <I>O</I>(<I>n </I>lg <I>n</I>).<P>
<P>







<h2><a name="09ed_1c3b">Exercises<a name="09ed_1c3b"></h2><P>
<a name="09ed_1c3c">35.2-1<a name="09ed_1c3c"><P>
Show that there may be <img src="../images/bound.gif">(<I>n<SUP>2</I></SUP>) intersections in a set of <I>n</I> line segments.<P>
<a name="09ed_1c3d">35.2-2<a name="09ed_1c3d"><P>
Given two nonintersecting segments <I>a</I> and <I>b</I> that are comparable at <I>x</I>, show how to use cross products to determine in <I>O</I>(1) time which of <I>a &gt;<SUB>x </SUB>b </I>or <I>b &gt;<SUB>x</SUB> a</I> holds.<P>
<a name="09ed_1c3e">35.2-3<a name="09ed_1c3e"><P>
<a name="09ed_1c32">Professor Maginot suggests that we modify <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECT</FONT> so that instead of returning upon finding an intersection, it prints the segments that intersect and continues on to the next iteration of the <B>for</B> loop. The professor calls the resulting procedure <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECTING</FONT>-S<FONT FACE="Courier New" SIZE=2>EGMENTs</FONT> and claims that it prints all intersections, left to right, as they occur in the set of line segments. Show that the professor is wrong on two counts by giving a set of segments for which the first intersection found by <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECTING</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT> is not the leftmost one and a set of segments for which <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECTING</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT> fails to find all the intersections.<P>
<a name="09ed_1c3f">35.2-4<a name="09ed_1c3f"><P>
<a name="09ed_1c33"><a name="09ed_1c34"><a name="09ed_1c35">Give an <I>O</I>(<I>n </I>lg<I> n</I>)-time algorithm to determine whether an <I>n</I>-vertex polygon is simple.<P>
<a name="09ed_1c40">35.2-5<a name="09ed_1c40"><P>
<a name="09ed_1c36">Give an <I>O</I>(<I>n </I>lg <I>n</I>)-time algorithm to determine whether two simple polygons with a total of <I>n</I> vertices intersect.<P>
<a name="09ed_1c41">35.2-6<a name="09ed_1c41"><P>
<a name="09ed_1c37"><a name="09ed_1c38">A <I><B>disk</I></B> consists of a circle plus its interior and is represented by its center point and radius. Two disks intersect if they have any point in common. Give an <I>O</I>(<I>n </I>lg <I>n</I>)-time algorithm to determine whether any two disks in a set of <I>n</I> intersect.<P>
<a name="09ed_1c42">35.2-7<a name="09ed_1c42"><P>
<a name="09ed_1c39"><a name="09ed_1c3a">Given a set of <I>n</I> line segments containing a total of <I>k</I> intersections, show how to output all <I>k</I> intersections in <I>O</I>((<I>n + k</I>) lg <I>n</I>) time.<P>
<a name="09ed_1c43">35.2-8<a name="09ed_1c43"><P>
Show how to implement the red-black-tree procedures so that <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECT</FONT> works correctly even if some segments are vertical or more than three segments intersect at the same point. Prove that your implementation is correct.<P>
<P>


<P>







<h1><a name="09ee_1c41">35.3 Finding the convex hull<a name="09ee_1c41"></h1><P>
<a name="09ee_1c3b">The <I><B>convex hull</I></B> of a set <I>Q</I> of points is the smallest convex polygon <I>P</I> for which each point in <I>Q</I> is either on the boundary of <I>P</I> or in its interior. We denote the convex hull of <I>Q</I> by CH(<I>Q</I>). Intuitively, we can think of each point in <I>Q</I> as being a nail sticking out from a board. The convex hull is then the shape formed by a tight rubber band that surrounds all the nails. Figure 35.6 shows a set of points and its convex hull.<P>
In this section, we shall present two algorithms that compute the convex hull of a set of <I>n</I> points. Both algorithms output the vertices of the convex hull in counterclockwise order. The first, known as Graham's scan, runs in <I>O</I>(<I>n </I>lg <I>n</I>) time. The second, called Jarvis's march, runs in <I>O</I>(<I>nh</I>) time, where <I>h</I> is the number of vertices of the convex hull. As can be seen from Figure 35.6, every vertex of CH(<I>Q</I>) is a point in <I>Q</I>. Both algorithms exploit this property, deciding which vertices in <I>Q</I> to keep as vertices of the convex hull and which vertices in <I>Q</I> to throw out.<P>
<img src="898_a.gif"><P>
<h4><a name="09ee_1c42">Figure 35.6 A set of points Q with its convex hull CH(Q) in gray.<a name="09ee_1c42"></sub></sup></h4><P>
<a name="09ee_1c3c">There are, in fact, several methods that compute convex hulls in <I>O</I>(<I>n</I> lg <I>n</I>) time. Both Graham's scan and Jarvis's march use a technique called &quot;rotational sweep,&quot; processing vertices in the order of the polar angles they form with a reference vertex. Other methods include the following.<P>
<a name="09ee_1c3d"><img src="../images/dot12.gif">     In the <I><B>incremental method</I></B>, the points are sorted from left to right, yielding a sequence &lt;<I>p</I><SUB>1</SUB>,<I>p</I><SUB>2</SUB>, . . . , <I>p<SUB>n</I></SUB>&gt;<I><SUB></I></SUB>. At the <I>i</I>th stage, the convex hull CH({<I>p</I><SUB><FONT FACE="Courier New" SIZE=2>1</FONT></SUB>, <I>p</I><SUB><FONT FACE="Courier New" SIZE=2>2</FONT></SUB>, . . . , <I>p<SUB><FONT FACE="Courier New" SIZE=2>i</I>-1</FONT></SUB>}) of the <I>i </I>- 1 leftmost points is updated according to the <I>i</I>th point from the left, thus forming CH({<I>p</I><SUB><FONT FACE="Courier New" SIZE=2>1</FONT></SUB>, <I>p</I><SUB><FONT FACE="Courier New" SIZE=2>2</FONT></SUB>, . . . , <I>p<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB>}). As Exercise 35.3-6 asks you to show, this method can be implemented to take a total of <I>O</I>(<I>n</I> lg <I>n</I>) time.<P>
<a name="09ee_1c3e"><img src="../images/dot12.gif">     In the <I><B>divide-and-conquer method</I></B>, in <img src="../images/bound.gif">(<I>n</I>) time the set of <I>n</I> points is divided into two subsets, one of the leftmost <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> points and one of the rightmost <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> points, the convex hulls of the subsets are computed recursively, and then a clever method is used to combine the hulls in <I>O</I>(<I>n</I>) time.<P>
<a name="09ee_1c3f"><img src="../images/dot12.gif">     The <I><B>prune-and-search method</I></B> is similar to the worst-case linear-time median algorithm of Section 10.3. It finds the upper portion (or &quot;upper chain&quot;) of the convex hull by repeatedly throwing out a constant fraction of the remaining points until only the upper chain of the convex hull remains. It then does the same for the lower chain. This method is asymptotically the fastest: if the convex hull contains <I>h</I> vertices, it runs in only <I>O</I>(<I>n</I> lg <I>h</I>) time.<P>
<a name="09ee_1c40">Computing the convex hull of a set of points is an interesting problem in its own right. Moreover, algorithms for some other computational-geometry problems start by computing a convex hull. Consider, for example, the two-dimensional <I><B>farthest-pair problem:</I></B> we are given a set of <I>n </I>points in the plane and wish to find the two points whose distance from each other is maximum. As Exercise 35.3-3 asks you to prove, these two points must be vertices of the convex hull. Although we won't prove it here, the farthest pair of vertices of an <I>n</I>-vertex convex polygon can be found in <I>O</I>(<I>n</I>) time. Thus, by computing the convex hull of the <I>n</I> input points in <I>O</I>(<I>n</I> lg <I>n</I>) time and then finding the farthest pair of the resulting convex-polygon vertices, we can find the farthest pair of points in any set of <I>n</I> points in <I>O</I>(<I>n</I> lg <I>n</I>) time.<P>