计算机算法基础 第2版 习题及答案 第12章

PAGE22第12章 计算几何基础给定以下X-Y平面上两个向量，求它们的点积和叉积：p1=(4,-6)，p2=(-2,7)p1=(0,8)，p2=(5,-2)解：(a) p1·p2=4-6·-27=- p1´p2=4-2-67=28(b) p1·p2=08·5-2= p1´p2=058-2假设平面上四个点p1，p2，p3，p4的坐标如下，用叉积判断线段p1p2和p1=(3,5)，p2=(-4,6)，p3=(-2,-1)和p4=(1,-5)p1=(-1,8)，p2=(5,-1)，p3=(1,6)和p4=(-4,-7)解：(a) p1=(3,5)，p2=(-4,6)，p3=(-2,-1)和p4=(1,-5)d1=(p2–p1)(p3–p1)=x2-x1xd2=(p2–p1)(p4–p1)=x2-x1x4因为d10，显然不共线。又因为d1d2>0所以两线段不相交。pp3p4p2p1O(b) p1=(-1,8)，p2=(5,-1)，p3=(1,6)和p4=(-4,-7)d1=(p2–p1)(p3–p1)=x2-x1x3-xd2=(p2–p1)(p4–p1)=x2-x1x4-x1y2d3=(p4–p3)(p1–p3)=x4-x3x1-d4=(p4–p3)(p2–p3)=x4-x3x因为d10，显然不共线。又因为d1d2<0和d3d4<0，所以两线段相交。pp3p4p2p1O线段p1p2和p3p4相交但不共线有三种情况，即交点不与任何端点重合，交点与其中一个线段的一个端点重合，和交点与两个线段各有一个端点重合。书中算法Segment-Intersect不给予分类。请修改书上算法使得每种相交类型得以确定，并指明交点与哪一个端点或哪两个端点重合解： 修改后算法如下，正确性显然。Modified-Segment-Intersect(p1,p2,p3,p4) //p1p2和d1(p2–p1)(p3–p1)d2(p2–p1)(p4–p1)d3(p4–p3)(p1–p3)d4(p4–p3)(p2–p3)ifd1=d2=0 //p1p2和p3p4共一直线，此时必有d3 then ifx1=x2 then ifmax{y1,y2}<min{y3,y4}ormax{y3,y4}<min{y1,y2} thenreturnfalse //不相交 elsereturntrue //相交 endif else ifmax{x1,x2}<min{x3,x4}ormax{x3,x4}<min{x1,x2} thenreturnfalse //不相交 elsereturntrue //相交 endif endif else if(d1d2>0)or(d3d4>0) thenreturnfalse //不相交 elsecase //相交 (1)(d1d2<0)and(d3d4<0) return(true,交点不与任何端点重合) (2)(d1d2<0)and(d3=0)and(d40) return(true,交点只与p1重合) (3)(d1d2<0)and(d4=0)and(d30) return(true,交点只与p2重合) (4)(d3d4<0)and(d1=0)and(d20) return(true,交点只与p3重合) (5)(d3d4<0)and(d2=0)and(d10) return(true,交点只与p4重合) (6)(d1=0)and(d3=0) return(true,交点与p1和p3重合) (7)(d1=0)and(d4=0) return(true,交点与p2和p3重合) (8)(d2=0)and(d3=0) return(true,交点与p1和p4重合) (9)(d2=0)and(d4=0) return(true,交点与p2和p4重合) endifendifEnd假设平面上有三个点，p1=(x1,y1)，p2=(x2,y2)，p3=(x3,y3)，用叉积表示以这三个点为顶点的三角形的面积。解： 假如p1，p2，p3是逆时针方向绕出的三角形的(也就是说，当沿这三点前行时，三角形是在这三条边左侧)，下面的图(a)表明这个三角形的面积为p1p2p3=Op1p2+Op2p3-Op1p3=12(p1´p2+p2´p3+p3´p1)。 注意，这里p3´p1是负值。所以有：p1p2p3=12(x1x2y1y2+x2x容易看出，只要p1，p2，p3是逆时针方向绕出的三角形的，不论图中夹角，，之间关系如何，公式(1)总是对的。读者可以用下面图(b)为例验证。如果p1，p2，p3是顺时针方向绕出的三角形的，那么公式仍然正确，但结果是个负值。另外，不论坐标原点O是在三角形外面还是里面，公式(1)和(2)总是对的。这是因为如果把坐标平移一个值，公式(2)的值不变:111a+x1a+x2a+x3=111x1x2x=111pp1p3(a)=+p2p1p3(b)=-p2OO平面一个点p1相对于以另一点p0为原点的极角(极坐标角)就是向量p1-p0在通常的极坐标中的角度。例如，点(3,5)相对于点(2,4)的极角就是向量(3,5)-(2,4)=(1,1)在极坐标中的角度，即45或p/4，而点(3,3)相对于点(2,4)的极角是向量(1,-1)在极坐标中的角度，也就是315或7p/4。现在，假设有一个n个点的序列<p1,p2,…,pn>以及另外一点p0，请设计一个复杂度为O(nlgn)的算法把这n个点按它们相对于点p0的极角从小到大排序，并且要求用叉积的方法比较两个点的极角而不是实际算出它们的极角。我们假定，没有一个点与点p0重合。解：算法的步骤解释如下：我们先计算v1=p1-p0，v2=p2-p0，…，vn=pn-p0。然后，把v1，v2，…，vn按它们在通常极坐标中的角度进行排序。我们用angle(v)表示点v的极角，X(v)和Y(v)表示点v的X-坐标和Y-坐标。假设p1=(x1,y1)，p2=(x2,y2)是其中两个点，我们知道，如果p1p2>0，p2是在p1的逆时针方向上，那么，我们能否讲angle(p2)>angle(p1)呢？不一定，这个结论成立当且仅当|angle(p2)-angle(p1)|<180°。下面图解释了这个关系。所以，在我们的算法中，我们先把各点按它们的Y-坐标分组:Y-坐标等于零并且角度为0的点归入第一组，Y-坐标大于零的点为第二组，Y-坐标等于零并且角度为180的点归入第三组，Y-坐标小于零的点为第四组。这样一来，各组中任两点的角度差都小于180°，我们只需把第二和第四组中点排序后，把四个组顺序连上即可。对各组中的点排序可以用任何一个复杂度为O(nlgn)的比较排序算法，例如合并排序。我们只要改动Merge部分中一行即可，即把A[i]B[j]改为叉积A[i]B[j]0，并假定数组A和B是点的序列而不是数字序列。我们把这个排序算法称为Modified-Merge-Sort，细节省略。p1p2>0时两点极坐标角度的关系 算法的伪码如下，复杂度显然为O(nlgn)。Angle-Sort(p0,p[1..n],G[1..n]) //G[1..n]是输出序列fori¬1ton vi=pi-p0endforG1¬G2¬G3¬G4¬Æfori¬1ton ifY(vi)=0 //点vi的Y坐标 then ifX(vi)>0 //点vi的X坐标 thenG1¬G1È{v elseG3¬G3È{v endif else ifY(vi)>0 thenG2¬G2È{v elseG4¬G4È{v endif endifendforModified-Merge-Sort(G2)Modified-Merge-Sort(G4)G[1..n]G1G2G3G4 //End设计一个O(n2lgn)的算法以判定平面上n个不同点中是否有三个点共线。解： 假设有三个点共线并有顺序a、b、c，那么点b和点c相对于点a的极角相等。所以，如果我们把点a以外的n-1个点按相对于a的极角排序的话，一定会发现点b和点c相对于点a的极角相等。根据第5题的答案，这个排序需时O(nlgn)。但是，怎样才能找到a呢？一个简单方法就是把每个点都当成a来试一下，总能把a找到。这样的话，总共需要O(n2lgn)时间。假设这n个点存放在集合S中，这个算法的伪码如下：Three-Co-linear(S，n)foreachvS p0¬v p[1..n-1]¬S–{v} Angle-Sort(p0，p[1..n-1]，G[1..n-1]) //调用第5题中算法 fori¬1ton-2 if(G[i]-p0)(G[i+1]-p0)=0 thenreturn(yes，p0，G[i]，G[i+1]) endif endforendforreturn(No)End设计一个时间为O(nlgn)的算法来判定一个n个顶点的多边形是个简单多边形。为简单起见，假设没有垂直于X轴的边。解： 我们只要检查这个多边形的n个边，除相邻两条边有共同端点外，互相不相交即可。设这个多边形的n个点的集合是V={v1，v2，…，vn)。假设这个多边形的n个边对应的线段是:e1=(u1，w1)，e2=(u2，w2)，…，en=(un，wn)，并假定ui是ei的左端点，wi是ei的右端点(1in)。因没有垂直于X轴的边，可假设ui的X坐标X(ui)小于wi的X坐标X(wi)，X(ui)<X(wi)(1in)。我们用平扫线方法去判定有无线段相交。如第12.2.1节讨论的，我们先把2n个端点从左到右排序成事件点调度L[1..2n]。为了叙述的方便，我们用L[k]=ui表示事件点L[k](1k2n)是边ei的左端点，用L[k]=wi表示L[k]是边ei的右端点，用V(L[k])=vj表示L[k]是集合V中顶点vj。显然，从L[k]可确定该事件点是哪个边的左端点，或哪个边的右端点，以及V中哪个顶点，并且只需O(1)时间。我们注意到，如果这个多边形是个简单多边形的话，V中每一个顶点出现在事件点调度L[1..2n]中正好两次，否则不是简单多边形。我们把第12.2.2节的平扫线方法稍作改动，来判断这个多边形的n条边有无相交。详细算法如下。改动之处，有注解说明。Simple-Polygon(S,n) //S是n个线段的集合T //建一个空的红黑树。按第12.2.1节讨论以及上面的解释，把2n个端点从左到右排序成事件点调度L[1..2n]fork1to2n-2 ifV(L[k])=V(L[k+1])=V(L[k+2]) thenreturn(notsimple) //这一步查有无三个端点重合 endifendforfork1to2n-2 //最后两端点不需查 ifL[k]=ui then sei //L[k]是边ei的左端点ui Insert(T,s) ifAbove(T,s)existsandAbove(T,s)=ej then if(ujui)and(wjui)and(ejintersectsei) thenreturn(notsimple) endif endif ifBelow(T,s)existsandBelow(T,s)=ej then if(ujui)and(wjui)and(ejintersectsei) thenreturn(notsimple) endif endif endif ifL[k]=wi //L[k]是边ei的右端点wi then sei ifAbove(T,s)existsandAbove(T,s)=ej then ifBelow(T,s)existsandBelow(T,s)=eh thenif(wjwh)and(ejintersectseh) thenreturn(notsimple) endif //只有ej和eh右端点有可能重叠 endif Delete(T,s) endifendforreturn(simple)End算法第2步的排序需要O(nlgn)时间，第3行的for循环需要O(n)时间，第8行的for循环需要执行O(n)次红黑树的插入或删除操作，而每次红黑树的操作需要O(lgn)时间，所以，算法的复杂度是O(nlgn)。一个园盘就是一个园心和半径定义的一个园再加上它的内部，即由该园所包围的点集。两个园盘如果有任何公共点，则称为相交。设计一个复杂度为O(nlgn)的算法以确定在n个给定的园盘中是否有两个园盘相交。解： 假设我们用(p,r)代表一个园盘，这里p是该园盘的园心点而r是其半径。如下图(a)所示，园盘(p1,r1)和园盘(p2,r2)相交当且仅当|p2-p1|=(x1-x2)2+(y1-y2)2£r1+r2。这里，p1=(x1,y1)，p2=(x2,我们用平扫线的方法来寻求答案。设园盘(p,r)的园心p有坐标p=(x,y)，我们用它的平行于X轴的直径(一个线段)来表示这个园，它的左端点为u=(x-r,y)，而右端点为v=(x+r,y)。我们假定对应于这n个园盘的直径的线段为D1=(u1,v1)，D2=(u2,v2)，…，Dn=(un,vn)。我们把这2n个端点按X坐标由小到大排序。如果有多个端点有相同的X坐标，那么左端点排在右端点前面。如果有多个右端点或左端点有相同的X坐标，那么有较小Y坐标的点排在前面。我们假定没有两端点同时有相同的X坐标和Y坐标，因为这表示两个园盘相交。这2n个端点称为事件点，并用X(v)表示事件点v的X坐标。当平扫线l从左到右经过每个事件点v时，我们检查和更新它的状态，这里，状态指的是按Y坐标从大到小排好序的所有与l相交的直径的序列。我们的算法与书中第12.2.2节的确定线段相交的算法类似，具体操作如下：如果v是某直径D的左端点时，把D插入到当前的状态中，并检查状态中与v相邻的直径对应的园盘是否与D所对应的园盘相交。当v是直径D的右端点时，把D从当前的状态中刪去并检查状态中与v相邻的上下两直径对应的园盘是否相交。算法的伪码如下：Disk-Intersect(S,n) //S是n个园盘的集合T¬Æ //平扫线初始状态为空，红黑树初始为空计算n个直径并将2n个端点按X坐标排序为p[1..2n] //假定没有两端点重合fori1to2n ifp[i]是某直径D的左端点 then Insert(T,D) //把D插入平扫线状态 if(Above(T,D)existsandintersectsD) //指对应园盘相交 thenreturntrue,D,Above(T,D) endif if(Below(T,D)existsandintersectsD) thenreturntrue,D,Below(T,D) endif else //p[i]是某直径D的右端点 ifAbove(T,D)andBelow(T,D)existandintersect thenreturntrue,Above(T,D),Below(T,D) endif Delete(T,D) endifendforreturnfalseEnd和书上一样，我们用红-黑树作为T的数据结构，这个算法的复杂度为O(nlgn)。至于它的正确性，我们只需证明，如果两园盘相交，一定会报告相交。下面我们证明，如果两园盘相交，一定会在平扫线的某状态中有两个相邻直径所对应的园盘相交。因为算法检查每个平扫线的状态中所有相邻直径所对应的园盘是否相交，所以一定会报告相交。假设两相交园盘各有直径D1=(u1,v1)和D2=(u2,v2)，不失一般性，设Y(u2)Y(u1)。那么在点u1的平扫线会穿过D2或者在点u2的平扫线会穿过D1。不失一般性，设在点u1的平扫线穿过D2，交点为y。我们分两种情况讨论：点u1在园盘D2内，如下图(a)所示。这时平扫线在点u1的状态中，如果D1和D2相邻，则正确性得证。否则，在点u1的状态中必有在D1和D2之间的直径，其中必有一个直径D与D2相邻。因为直径D出现在点u1的状态中，那么直径D必与线段u1y相交，因而它对应的园盘与园盘D2相交，因此，算法会报告相交。这里，y是平扫线与D2的点u1不在园盘D2内，如下图(b)所示。这时线段u1y与D2的园周相交于点z。设点w是园盘D1与D2相交的最左边点。这时平扫线在点u1的状态中，如果D1和D2相邻，则正确性得证。否则，在点u1的状态中必有在u1和u2之间的直径，它们或与线段zy相交，或与u1z相交。如果有直径与线段zy相交，那么与D2相邻的那个直径对应的园盘与园盘D2相交，正确性得证。如果没有直径与线段zy有直径D与u1z相交但都不在三角形u1wz中终止。那么它们必定与园盘D1或D2相交。所以与D1或D2相邻的直径中必有一个与D1或D2有直径D与u1z相交并在三角形u1wz中终止的。如图(b)所示，也许还有两个端点都包含在三角形u1wz中的直径。设x是在这些直径中最右边的一个端点的X坐标。那么在平扫线到达点x并更新在点x的状态时，要么算法已经报告有园盘相交，要么把最后一个端点在x的直径刪去后，D1和D2相邻。uu1D1v2D2v1u2平扫线zwDy(b) 直径D1左端点u1不在园盘D2内v2D2u1D1v1yu2平扫线(a) 直径D1左端点u1在园盘D2内两园盘相交时的两种情况图示假设线段a和b在点x可比较，a和b都不垂直于X轴并且它们也不相交。下面的图给出了一个例子。请设计一个程序在O(1)时间内确定是a>xb还是b>xa。解： 已知a和b不相交并且都和直线x相交，我们可假定a的两端点为p1=(x1,y1)和p2=(x2,y2)，并且x1£x£x2，而b的两端点为p3=(x3,y3)和p4=(x4,y4)，并且x3£x£x4。伪码如下：Above(p1,p2,p3,p4) d1¬(p2–p1)´(p3–p1)d2¬(p2–p1)´(p4–p1)d3¬(p4–p3)´(p1–p3)d4¬(p4–p3)´(p2–p3)if(d1<0andd2<0) //p1p3和p1p4同在 or(d3>0andd4>0) //或者p3p1和p3p2 thena>xb elseb>xaendifEnd另外一个办法是把两线段与垂直线x的交点算出来后做比较。某教授建议用下面的算法决定一个n个顶点的序列<p0，p1，…，pn-1>是否是一个凸多边形的连续顶点：如果集合{Ðpipi+1pi+2|i=0,1,…,n-1}不同时含有左拐和右拐，那么回答是，否则回答不是。这里对足标的加法是以n为模加法，即和数大于等于n时，除以n后取余数。请证明，这个算法虽然是个线性算法，但不能始终得到正确答案。请修改这个算法使其始终能在线性时间内得到正确答案。解： 下面的图显示了一个反例。集合{Ðpipi+1pi+2|i=0,1,…,n-1}不同时含有左拐和右拐是个必要条件但不充分。我们需要加上一些额外条件才行。让我们假设集合{Ðpipi+1pi+2|i=0,1,…,n-1}不含有右拐。对于不含左拐的情形可对称处理。我们注意到，如果序列<p0，p1，…，pn-1>是一个凸多边形的连续顶点，那么，任一个子序列，<p0，p1，…，pi>(2in-1)，也必定构成一个凸多边形。当i=2时，<p0，p1，p2>显然是一个凸多边形(三角形)。我们要探讨的是，如果子序列，<p0，p1，…，pi>(2in-2)，构成一个凸多边形，那么点pi+1需要满足什么条件使子序列<p0，p1，…，pi，pi+1>也构成一个凸多边形？从下面的图中可以看出这个额外条件是：Ðpipi+1p0和Ðpi+1p0p1必须不向右拐。综上所述，n个顶点的序列<p0，p1，…，pn-1>是一个凸多边形的连续顶点的条件是：集合{Ðpipi+1pi+2|i=0,1,…,n-1}{Ðpipi+1p0|i=2,3,…,n-2}{Ðpi+1p0p1|i=3,4,…,n-2}不同时含右拐和左拐。因为检查一个角度是左拐还是右拐只需O(1)时间，这个修改后的算法仍然只需O(n)时间。给定平面上一点p0=(x0,y0)，以这点为起点的右水平射线(righthorizontalray)，R(p0)，是从p0开始的与X轴平行的半条直线，即R(p0)={(x,y)|y=y0，xx0}。请用判断线段相交的方法在O(1)时间判断一个线段p1p2是否与R(p0解： 下图显示了线段p1p2与R(p0)假定交点在(x,y0)，那么必有x0£x£max(x1,x2)。记x’=max(x1,x2)，那么点p=(x’,y0)是R(p0)上一点。线段p1p2与R(p0)的交点就是p1p2与p0p的交点。所以判断线段p1pIntersect(p0,p1,p2) //p0=(x0,y0),p1=(x1,y1),p2=(x2,y2)x’max(x1,x2)p(x’,y0)ifSegment-Intersect(p0,p,p1,p2)=true thenreturntrue elsereturnfalseendifEnd注意，有可能x’<x0，这时p1p2不可能与R(p0)相交，也不会与假设一多边形的顶点按反时针方向的顺序是áp1,p2,…,pnñ，这里pi=(xi,yi)(1£i£n)。假设这个多边形是一个凸多边形，设计一个O(n)算法来判断点p0=(x0,y0)是否在这个多边形内部(在边界上的点不算在内部)。为简单起见，我们假定x0¹xi(1£i£n)和y0¹yi(1£i£n)。假设这个多边形是个简单多边形，但不一定是凸多边形，其他同(a)，重做(a)部分问题。解: (a) 我们只需要检查pip0是否是在pipi+1左边(1£i£n-1)以及p伪码如下：Convex-Inclusion(p[1..n],p0)fori¬1ton-1 if(pi+1–pi)´(p0–pi)0 thenreturn(notinside) endifendforif(p1–pn)´(p0–pn)0 thenreturn(notinside) elsereturn(yes,inside)endifEnd(b) 考虑一条从p0开始的右水平射线(定义见题11)。点p0在多边形内当且仅当R(p0)与该多边形的奇数条边相交。因为假定y0yi(1≤i≤n)，边pipi+1与R(p0)相交必有yi<y0<yi+1或者yi+1<y0<yi。这里，i+1=(imod(b.1) 如果yi<y0<yi+1，那么pipi+1与R(p0)相交当且仅当pip0(b.2) 如果yi+1<y0<yi，那么pipi+1与R(p0)相交当且仅当pip0根据以上分析，伪码如下：Simple-Polygon-Inclusion(p[1..n],p0) //顶点序列可以是反时针或正时针方向c¬0 //记录相交次数fori¬1ton j(imodn)+1 if(yi<y0<yj)and(pj–pi)´(p0–pi)>0 thenc¬c+1 elseif(yj<y0<yi)and(pj–pi)´(p0–pi)<0 thenc¬c+1 endif endifendforifcmod2=1 thenreturn(Yes,inside) elsereturn(No,notinside)endifEnd*假设一个简单多边形的逆时针方向的顶点序列是<p0，p1，…，pn-1>。请设计一个时间复杂度为O(n)的算法来计算这个多边形所围的面积。注意，这个多边形不一定是凸多边形。解： 因为坐标平移不影响面积，我们可假定原点在多边形内部。下图(a)显示，如果这个多边形是个凸多边形，那么，其所围的面积等于一系列三角形面积相加。但是，如果这个多边形不是个凸多边形，那么，如下图(b)显示，其所围的面积等于一系列三角形面积的代数和，其正负号正好等于对应叉积的正负号。所以这个多边形所围的面积有如下公式：面积S=12i=0n-1(pioop0p1一p2p3p4(b) 非凸多边形情形op0p1p2p3p4(a) 凸多边形情形p5算法的伪码如下：Polygon-Area(p0,p1,…,pn-1)s0fori1ton-1 ss+12returnsEnd注意，不论原点在哪里，在多边形内部或外部，这个面积公式S=12i=0n-1(pi×pi+1modn)都是正确的。这是因为，如果我们把原点平移到任何位置，相当于把每一个顶点pi=(xi,yi)(0in-1)平移到pi’=(xi+a,yi+b)，这里，a和b可以是任意实数。下面我们证明，i=0n-1(pii=0n-1(pi=i=0n-1x=i=0n-1xixi+1y=i=0n-1xixi+1yi=i=0n-1xixi+1yiy=i=0n-1xixi+1=i=0n-1xix=i=0=i=0n-1假设点q是一个简单多边形P的边界上一点，如果线段qr上所有点都在P的内部或边界上，那么点r称为q的一个阴影点。点q的所有阴影点的集合称为q的阴影(Shadow)。如果P中存在一个点p，它是所有P的边界上点的阴影点，那么这个点p称为是P的核心点，而P被称为一个星形多边形(star-shaped)。所有核心点的集合称为核心(kernel)。下图给出了星形多边形和非星形多边形例子。假设P是一个n个顶点的星形多边形，它的逆时针方向的顶点序列是<p0,p1,…,pn-1>。请设计一个O(n)算法计算它的凸包CH(P)。星形多边形示例解： 下面这个算法与Graham扫描法相似。不同处是，这个算法不用极角排序而是直接用给定的顶点序列。不失一般性，假设p0是Y坐标最小的顶点。如果有几个这样的点，则取有最小X坐标的一个点为p0。显然，p0必定是CH(P)中一个点。现在，假设P的逆时针方向的顶点序列是<p0，p1，…，pn-1>。算法的伪码如下：Convex-Hull-Star-Shaped-Polygon(p[0..n-1])//InitializationS //堆栈清空Push(S,p0)Push(S,p1) //初始化完成fori2ton(modn) qTop(S) pNext-to-top(S) while(q–p)(pi–p)0 //由点p到点q后，再到点pi时，不向左拐 Pop(S) qp pNext-to-top(S) endwhile Push(S,pi)endforreturnSEnd 算法的复杂度显然是O(n)，因为压栈动作为n-1次而弹出动作少於n-1次。下面证明正确性。因为P是一个星形多边形，如图(a)所示，它有一个核心点p。当我们沿着P的逆时针方向的顶点序列<p0，p1，…，pn-1>移动一个点x时，因为xp在多边形P内部或边界上，所以由点p和任何一条边pkpk+1modn(0kn-1)组成的三角形都必定包含在凸包之内。显然，由点p和连续的两条边，pkpk+1和pk+1pk+2modn(0kn-2)组成的四边形也必定包含在凸包里。因此，当点x沿着边pkpk+1移动到点pk+1时，如果转到边pk+1pk+2modn上去时向右转，那么，如图(a)所示，点pk+1一定在由点p,点pk和点pk+2组成的三角形内部。因此，点pk+1注意，p0在堆栈中头尾各出现一次。另外，如果多边形不是星形多边形，这个算法可能出错，下图(b)给出了这样一个例子。在用分治法计算最近点对的算法中，在分治法合(combine)的过程中，我们为数组Y*中每个点检查7个与之相邻的点。请证明实际上只需检查5个与之相邻的点即可。证明： 因为在书中图12-14所示的2矩阵中最多可以有8个点，所以与任一个点距离小于的点最多是7个。但是，这8个点中有两个点与其他两个点重合。如果不算重合的点，只有6个不重合的点。所以，如果没有重合的点，那么只需检查5个与之相邻的点即可。那么，如果有重合的点，检查5个与之相邻的点能行吗？答案是没有问题。这是因为，如果有两点重合，那么在检查到这两个重合点时，它们的Y-坐标相等，从图12-14可知，Y坐标相等的点最多有4个，因此，一定在3个与之相邻的点中会发现有两点重合而得到=0。*假设一个凸多边形P的反时针方向的顶点序列是<p0，p1，…，pn-1>(n3)。请设计一个O(n)的算法找出P的直径，即最大的两顶点间距离。解： 假设di是顶点pi(0in-1)和其他顶点间最大距离，那么P的直径为max0≤i≤n-1{di}。但是，如果计算每一个顶点和pi的距离，则需要(n)时间得到di，从而需要(n2)时间得到P的直径。下面介绍一个快速方法。我们想象把P沿着水平初始化：在滚动开始时，设线段p0p1与水平底线置全局变量diameter=0。直径两端u，v暂无定义，即unil，vnil。变量diameter记录当前发现的顶点间最大距离。用下面算法，寻找下标最小，但在线段p0p1的垂直平分线左边的顶点pkk2 while|p0–pk|>|p1–pk| //|p0–pk|表示p0和pk间距离 k(k+1)modn //pk可能等于p2，也可能等于p0endwhile //初始化完成滚动中对每个事件点的处理：在滚动中，顶点p1，…，pn-1会顺序接触底线，称为事件点。当顶点pj(1jn-1)接触底线时，我们计算顶点pj(2jn-1)和其他顶点间的距离。一旦发现某距离比全局变量diameter大，则更新这个全局变量。为了使计算复杂度小，我们只计算有可能大于全局变量的距离。如果顶点pj和某顶点x之间的距离肯定小于最大距离，则跳过不计算。关键是如何进行删减。如下图(a)所示，当顶点pj(1jn-1)接触底线时，如果顶点x在线段pj-1pj的垂直平分线的右侧，则不需计算pj和x的距离|pj-x|。这是因为|pj-x|<|pj-1-x|，它不可能是最大距离。假设顶点pk是逆时针方向第一个在垂直平分线左侧的点，那么从点pk开始，沿逆时针方向，逐点计算与点pj的距离，直到顶点ph为止。这里，点ph是从点pk开始，沿逆时针方向，第一个顶点使得|pj–ph|<|pj+1–ph|。如下图(b)所示，这是因为从点ph开始，所有点都在线段pjpj+1的垂直平分线的左侧pk-1

pk+1

pkp

(a)

pj

ph

pj-1

pk(b)

pj+1

pj-1

pj

pj+1

实际上，这意味着，新的事件点到来了，点pj+1开始接触底线，而点ph是是反时针方向第一个在pjpj+Diameter(p0，p1，…，pn-1)diameter0 //初始化直径为0unilvnil //u,v是当前找到的最大距离的两个端点，暂无定义k2while|p0–pk|>|p1–pk| k(k+1)modn //pk可能等于p2，也可能等于p0endwhile //初始化完成forj1ton jjmodn while|pj–pk||p(j+1)modn–pk| if|pj–pk|>diameter then diameter|pj–pk| upj vpk endif k(k+1)modn endwhileendforreturn(diameter,u,v)End算法的复杂度可分析如下。因为第8行的for循环中，j的序号增长n次，而序号k只增不减。因为序号k对应的点pk不会超越点pj，所以，序号k增加的次数不会大於开始与序号j的距离，再加n次。所以序号k增加的次数不会大於2n。所以第10行的比较次数总共不会超过2n次。因为第8行开始的for循环的主要工作是第10行的比较，而每次比较只需O(1)时间，所以算法的复杂度为O(n)。第12.2.2节中用平扫线确定有线段相交的算法Any-Segments-Intersect有两个限制要求。一个是没有三个线段相交于一点，另一个是没有垂直于X轴的线段。假设没有这两个限制，当线段p1p2垂直于X轴时，设p1=(x1,y1)，p2=(x2,y2)，x1=x2，y1y2，我们把点p1当做左端点，把点p2当做右端点。另外，在决定平扫线在x=x1的状态时，我们把点p1作为平扫线和线段p1p2的交点来和其它线段排序。证明，这样处理后，即使没有这两证明： 当算法Any-Segments-Intersect报告有线段相交时显然是正确的，所以我们只需证明，只要有线段相交，算法一定会报告true。为此，让我们假设集合S中有线段a和b相交于点p，而p的X坐标，X(p)，是所有交点中X坐标最小的一个。我们分三种情况讨论：线段a和b的左端点均出现在点p的左边。线段a的左端点出现在点p的左边，而线段b的左端点与直线x=X(p)相交。线段a和b的左端点均与直线x=X(p)相交。 下图显示了这三种情况。 我们证明在这三种情况下，算法都会报告有交点。如果线段a和b的左端点均出现在点p的左边，我们考虑在点p左边最后一个事件点q的平扫线状态。线段a和b必定包含在点q的平扫线状态中。如果a和b在某个平扫线状态中相邻，那么它们必定被算法检查过并一定报告相交。如果a和b在所有平扫线状态中不相邻，那么一定有一条线段d在q点的平扫线状态中介于a和b之间。这时，有下面几种情况。(a.1)如果线段d的右端点在p点的右边，但是线段d不与点p相交。这种情况下，线段d必定与a或b相交，这样一来，点p就不是最左边的交点了，这不可能。(a.2)如果线段d的右端点在p点的右边，而且线段d与点p相交。这种情况下，三个线段，a，b，d交于p点。也许这样的线段d不止一条，它们都在线段a和b之间并相交于点p。那么，平扫线在点q删去所有以点q为右端点的线段后，会发现线段a，b，以及d这样的线段中，有两个相邻，从而算法一定会报告有线段相交于p点。(a.3) 如果线段d的右端点正好在q点的平扫线上(包括d垂直于X轴的情况)，那么，d的右端点是个事件点，算法会在这个事件点上把线段d删去而使a和b相邻并得到相交的结果。如果a的左端点出现在点p的左边，而b的左端点与直线x=X(p)相交，那么有两种情况。(对称情况略去。)(b.1) 线段b不垂直于X轴。这种情况下，b的左端点必与交点p重合，并且是一个事件点。当算法对这个事件点进行操作时，如果算法还没有发现有相交的线段，那么，算法会把b插入到平扫线状态中。并发现b与a相邻。显然，算法会报告a和b相交。(b.2)线段b垂直于X轴。这种情况下，b的左端点是一个事件点。算法在亊件点x=X(p)会把b插入到平扫线状态中。如果b与a相邻，算法会报告a和b相交。如果b与a不相邻，那么在该点的状态序列中，b的左端点一定在点p的下面，并且b的左端点和点p之间有其它线段。因为这些线段都与线段b相交，那么算法会报告与b相邻的那个线段与b相交。如果线段a和b的左端点均与直线x=X(p)相交，那么线段a和b的左端点都是亊件点。在亊件点x，线段a和b被先后插入。不妨设a和b的左端点的Y坐标分别是Y(a)和Y(b)，并有Y(a)Y(b)。根据算法，线段a先被插入，有3种情况(对称情况略去)。(c.1)线段a和b都不垂直于X轴。这种情况下，a和b的左端点必定相交于点p，那么在插入b时，如果算法还没有报告有相交