2011算法第十六、十七講 幾何掃描

ECNUYinpingLiu幾何掃描柳銀萍ECNUYinpingLiu幾何算法中，考慮的主要對(duì)象通常是二維、三維和更高維空間中的點(diǎn)、線段、多邊形和其他幾何體。有時(shí)候一個(gè)問題的解法要求“掃描”給出的輸入對(duì)象來收集信息以找到可行解。這種技術(shù)在二維平面稱為平面掃描，在三維空間稱為空間掃描。在它的簡(jiǎn)單形式中，一條垂直的直線在平面中從左到右掃描，在每個(gè)對(duì)象(比如說一點(diǎn))處逗留，從最左的對(duì)象開始直到最右的對(duì)象。我們結(jié)合計(jì)算幾何中的一個(gè)簡(jiǎn)單問題來闡明這種方法。ECNUYinpingLiu定義18-1

設(shè)P1=(x1，y1，)和P2=(x2，y2)是平面中的兩點(diǎn)，如果x1≤x2并且y1≤y2,，則稱P2支配P1，記為Pl<P2。定義18-2

設(shè)S是平面中的一個(gè)點(diǎn)集，點(diǎn)p∈S是極大點(diǎn)或最大點(diǎn)，如果不存在點(diǎn)q∈S，使得p≠q并且p<q。求極大點(diǎn)的問題有一個(gè)簡(jiǎn)單的算法，它是幾何掃描算法的一個(gè)很好的例子。

MAXIMALPOINTS：在平面上給定一個(gè)

n個(gè)點(diǎn)的集合S，確定S中的極大點(diǎn)。

ECNUYinpingLiu求解這個(gè)問題很容易，方法如下:

首先，我們把S中的所有點(diǎn)按照它們x坐標(biāo)的非升序排列，最右點(diǎn)(有最大x值的那點(diǎn))無疑是個(gè)極大點(diǎn)。算法從右到左掃描這些點(diǎn)，同時(shí)確定它是否在y坐標(biāo)上被先前掃描過的任何點(diǎn)所支配。這個(gè)算法在下面的算法MAXIMA中給出。ECNUYinpingLiu算法18.1MAXIMA

輸入：平面上n個(gè)點(diǎn)的集合S。

輸出：S中極大點(diǎn)集合M。

1．設(shè)A為S中按

x坐標(biāo)非升序排列的點(diǎn)的集合。如果兩個(gè)點(diǎn)有相同的

x

坐標(biāo)，則有較大

y

坐標(biāo)值的點(diǎn)出現(xiàn)在集合的前面

2．M←{A[1]}

3．maxy

←A[1]的

y

坐標(biāo)值ECNUYinpingLiu

4．forj←2ton5．(x，y)←A[j]6．ify>maxythen7．M=MU{A[j]}8．

maxy←y9．endifendforECNUYinpingLiu圖18.1展示了算法在一個(gè)點(diǎn)集上的狀態(tài)。如圖所示，極大點(diǎn)集合{a,b,c,d}形成一個(gè)階梯。作為一個(gè)例子，請(qǐng)注意e

僅由a支配，而f由a和b

支配，g

僅由c

支配。很容易看出算法MAXIMA的運(yùn)行時(shí)間主要由排序步驟決定，因此是O(nlogn)。上述的例子展示了平面掃描算法的兩個(gè)基本組成部分。首先，有一個(gè)事件點(diǎn)進(jìn)度表，它是一個(gè)x坐標(biāo)自右向左排序的序列，這些點(diǎn)定義了掃描線將會(huì)“逗留”的位置，在這里掃描線是垂直線。ECNUYinpingLiu在某些平面掃描算法中情況可能與前面的例子不同，它們的事件點(diǎn)進(jìn)度表可能需要?jiǎng)討B(tài)更新.并且,為了得到高效的實(shí)現(xiàn),可能需要比簡(jiǎn)單的數(shù)組和隊(duì)列更復(fù)雜的數(shù)據(jù)結(jié)構(gòu).平面掃描方法中的其他部分是掃描線狀態(tài)，這是掃描線上幾何對(duì)象的適當(dāng)描述。在上述例子中，掃描線狀態(tài)由最新探測(cè)到的極大點(diǎn)的“描述”組成。這個(gè)描述僅僅是它的y坐標(biāo)的值。在其他的幾何算法中，掃描線狀態(tài)可能需要以棧、隊(duì)列或堆等形式存儲(chǔ)所需要的相關(guān)信息。ECNUYinpingLiu2.幾何預(yù)備知識(shí)

在本節(jié)中，我們介紹本章中將要用到的計(jì)算幾何中一些基本概念的定義。這些定義大多是在二維空間的框架之內(nèi)，它們可以很容易地推廣到更高維空間中。一個(gè)點(diǎn)p由一對(duì)坐標(biāo)(x，y)表示，一條線段由它的兩個(gè)端點(diǎn)表示。如果p和q是兩個(gè)不同點(diǎn)，我們用記端點(diǎn)為p和q的線段。一條折線路徑∏是點(diǎn)p1，p2，…，pn的一個(gè)序列，使得是線段，1≤i≤n-1，如果p1=pn，我們稱∏(包括以∏為界的封閉區(qū)域)是一個(gè)多邊形。在這種情況下,點(diǎn)pi,1≤i≤n，稱為多邊形的頂點(diǎn)，而線段

,,…，

:稱為邊。ECNUYinpingLiu我們可以很方便地用一個(gè)存儲(chǔ)了各個(gè)頂點(diǎn)的環(huán)形鏈表來表示一個(gè)多邊形。在一些算法中，它用環(huán)形雙向鏈表表示。如果一個(gè)多邊形P的任意兩條邊除了在頂點(diǎn)處外均不相交，那么稱P是簡(jiǎn)單的；否則它是非簡(jiǎn)單的。圖18.2顯示了兩個(gè)多邊形，一個(gè)是簡(jiǎn)單的，另一個(gè)不是。圖18.2(a)簡(jiǎn)單多邊形(b)非簡(jiǎn)單多邊形圖18.3(a)凸多邊形(b)非凸多邊形ECNUYinpingLiu從現(xiàn)在開始，除非特別加以說明，否則我們始終假設(shè)多邊形是簡(jiǎn)單的。對(duì)于一個(gè)多邊形P，如果連接P中任意兩點(diǎn)的線段全部在P中，我們說P是凸的。圖18.3

顯示兩個(gè)多邊形，一個(gè)是凸的，另一個(gè)不是。設(shè)S是平面上的一個(gè)點(diǎn)集，我們定義包含了S中所有頂點(diǎn)的最小凸多邊形為S的凸包，記做CH(S)。CH(S)的頂點(diǎn)稱為包頂點(diǎn)，有時(shí)也稱為S的極點(diǎn)。設(shè)u=(x1，y1)，v=(x2，y2)

和w=(x3,y3)，由這三點(diǎn)形成的三角形帶符號(hào)面積是下面行列式的一半。ECNUYinpingLiu如果“u,v,w,u”構(gòu)成一個(gè)逆時(shí)針回路，則D是正的。在這種情況下，我們說路徑u,v,w

構(gòu)成一個(gè)左旋。如果u,v,w,u

形成順時(shí)針回路,則它是負(fù)的，在這種情況下，我們說路徑u,v,w

構(gòu)成一個(gè)右旋(見圖18.4)。D=0當(dāng)且僅當(dāng)三點(diǎn)共線，即三點(diǎn)在同一直線上。ECNUYinpingLiu圖18.4(a)左旋(b)右旋ECNUYinpingLiu3.計(jì)算線段的交點(diǎn)

在這一節(jié)，我們考慮以下問題。給出平面上n條線段的集合L={l1,l2,…ln}，找出交點(diǎn)的集合。我們將假設(shè)沒有垂直線段，沒有三條線段交于同一點(diǎn)。如果沒有這些假設(shè)，則只會(huì)使算法變得更復(fù)雜。設(shè)

li

和

lj

是L中的任意兩條線段，如果

li

與

lj

分別和橫坐標(biāo)為

x的垂直線交于點(diǎn)

pi和

pj

那么，倘若在橫坐標(biāo)為

x的垂線上點(diǎn)

pi在

pj

的上方，我們就說

li

在

lj

的上方，表示為

li

>x

lj，關(guān)系

>x

定義了所有與具有橫坐標(biāo)為x的垂線相交的線段集的全序。于是，在圖18.5中，我們有:l2>xll，l2>xl3，l3>yl2

和

l4>zl3ECNUYinpingLiu圖18.5關(guān)系>x

的說明算法首先將n條線段的2n個(gè)端點(diǎn)按它們橫坐標(biāo)的非降序進(jìn)行排列。在算法執(zhí)行過程中，一條垂直線從左到右掃描所有線段的端點(diǎn)和它們間的交點(diǎn)。它從空的關(guān)系開始，每遇到一個(gè)端點(diǎn)或一個(gè)交點(diǎn)，就改變序關(guān)系。具體地說，當(dāng)線從左到右掃描時(shí)，只要出現(xiàn)如下事件之一，序關(guān)系就改變。ECNUYinpingLiu

(1)遇到線段的左端點(diǎn)時(shí)；

(2)遇到線段的右端點(diǎn)時(shí)；

(3)遇到兩條線段的交點(diǎn)時(shí)。掃描線的狀態(tài)完全由序關(guān)系>x描繪，至于事件點(diǎn)的進(jìn)度表E，它包括這些線段已排序的端點(diǎn)加上它們的交點(diǎn)，這些交點(diǎn)是在線從左到右掃描時(shí)動(dòng)態(tài)地添加進(jìn)去的。算法在每種事件上所做的動(dòng)作如下:(1)當(dāng)遇到線段l的左端點(diǎn)時(shí)，l被加到序關(guān)系中。如果有一條線段l1，緊接在l上面同時(shí)l1和l相交，則它們的交點(diǎn)將被插入到事件點(diǎn)進(jìn)度表E中去。類似地，如果存在線段l2緊接在l下面同時(shí)l2和l相交則它們的交點(diǎn)也將被插入到E中去。ECNUYinpingLiu(2)當(dāng)遇到線段l的右端點(diǎn)p時(shí)，算法把l從序關(guān)系中移去。在這種情況中，算法會(huì)測(cè)試緊接在l上下的線段l1和l2，看它們是否可能1在p的右側(cè)一點(diǎn)q處相交。如果出現(xiàn)種情況，口會(huì)被插人到E中去.(3)當(dāng)遇到兩條線段的交點(diǎn)時(shí)，它們?cè)陉P(guān)系中的相對(duì)次序被翻轉(zhuǎn)。這樣，如果在它們的交點(diǎn)左邊有l(wèi)1>xl2，那么序關(guān)系要修改為l2>xl1。設(shè)l3和l4是緊接在交點(diǎn)p的上面和下面的兩條線段(見圖18.6)，換句話說，對(duì)于交點(diǎn)右面l3在l2上面而l4在l1

的下面(見圖18.6)。在這種情況下，我們檢查l2與l3和l1與l4相交的可能性。像前面一樣，如果存在交點(diǎn)，就把它們插入E中。ECNUYinpingLiu圖18.6在交點(diǎn)處翻轉(zhuǎn)兩條線段的次序事件點(diǎn)進(jìn)度表和掃描線的狀態(tài)所需的數(shù)據(jù)結(jié)構(gòu):

為了實(shí)現(xiàn)事件點(diǎn)進(jìn)度表E，我們需要一個(gè)支持以下運(yùn)算的數(shù)據(jù)結(jié)構(gòu):

·insert(p，E)：把點(diǎn)p插入到E中；

·delete-min(E)：返回具有最小z坐標(biāo)的點(diǎn)并把它從E中刪除.ECNUYinpingLiu堆這種數(shù)據(jù)結(jié)構(gòu)顯然能夠在時(shí)間O(1ogn)內(nèi)支持這兩種運(yùn)算。于是，E由堆實(shí)現(xiàn)，初始時(shí)它包含2n個(gè)已排序的點(diǎn)。每次掃描線向右移動(dòng)，橫坐標(biāo)最小的點(diǎn)被取出，像上面說明的那樣，當(dāng)算法探測(cè)到一個(gè)交點(diǎn)p時(shí)，把p插入E。掃描線的狀態(tài)S必須支持以下的運(yùn)算:

·insert(l，S)：把線段l插入到S中；

·delete(l，S)：從S中刪除線段l；

·above(l，S)：返回緊接在l上方的線段；

·below(l，S)：返回緊接在l下方的線段。ECNUYinpingLiu一種通常稱為字典的數(shù)據(jù)結(jié)構(gòu)在O(logn)時(shí)間內(nèi)支持上面的每個(gè)運(yùn)算。注意阿above(l,s)

或below(l,s)可能不存在，我們需要一個(gè)簡(jiǎn)單的測(cè)試(它沒包含在算法中)來處理這兩種情況。關(guān)于這一算法，一個(gè)更精確的描述在算法INTERSECTIONSLS中給出。在算法中，過程process(p)把p插入E中并輸出p。

算法18.2:INTERSECTIONLS

輸入：平面上n個(gè)線段集L={l1,l2,···,ln}。

輸出：L中線段的交點(diǎn)。ECNUYinpingLiu1.按橫坐標(biāo)的非降序排列端點(diǎn)，將它們插入堆E中(事件點(diǎn)進(jìn)度表)2.whileE非空3.p←delete-min(E)4.ifp是左端點(diǎn)then5.設(shè)l是左端點(diǎn)為p的線段6.insert(l，S)7.l1above(l，S)8.l2below(l，S)9.ifl與l1在點(diǎn)q1相交thenprocess(q1)10.ifl與l2在點(diǎn)q2相交thenprocess(q2)ECNUYinpingLiu11.elseifp是右端點(diǎn)

then12.設(shè)l是右端點(diǎn)為p的線段13.l1←above(l,S)14.l2←below(l,S)15.

delete(l,S)16.

ifl1與

l2在

p的右邊點(diǎn)

q相交

thenprocess(q)17.else{p是相交點(diǎn)}18.設(shè)在p點(diǎn)相交的線段為l1和l219.其中l(wèi)1在p的左邊位于l2上方20.l3←above(l1,S){在p的左邊}21.l4←below(l2,S){在p的左邊}ECNUYinpingLiu22.ifl2與l3在q1相交thenprocess(q1)23.ifl1與l4在q2相交thenprocess(q2)24.在S中交換l1和l2的秩序25.endif26.endwhileECNUYinpingLiu排序步驟要耗費(fèi)O(nlogn)時(shí)間，設(shè)交點(diǎn)數(shù)是m，那么有2n+m個(gè)事件點(diǎn)要處理，每一點(diǎn)需要O(1og(2n+m))處理時(shí)間，因此，算法處理所有交點(diǎn)的總時(shí)間是O((2n+m)log(2n+m))。因?yàn)閙≤n(n-1)/2=O(n2)，階就變成O((n+m)1ogn)。由于找出全部交點(diǎn)用樸素的方法要運(yùn)行O(n2時(shí)間，因此這算法不適合于處理交點(diǎn)數(shù)目預(yù)計(jì)為

O(n2/logn)線段集合。另一方面，如果m=O(n)，則算法需要

O(n1ogn)

時(shí)間。算法的時(shí)間復(fù)雜度：ECNUYinpingLiu4.凸包問題

本節(jié)我們考察也許是計(jì)算幾何中最基本的問題：在平面中給出n個(gè)點(diǎn)的集合S，尋找S的凸包CH(S)。我們?cè)谶@里敘述一個(gè)著名的被稱為“Graham掃描”的幾何掃描算法。在它的簡(jiǎn)單形式中，Graham掃描使用以某一點(diǎn)為中心的掃描線，它旋轉(zhuǎn)掃描線使之掃過整個(gè)平面，并在每一點(diǎn)逗留以決定這一點(diǎn)是否將被包括到凸包中。首先,算法在點(diǎn)表上做一次掃描，找出具有最小y坐標(biāo)的點(diǎn)，記做p0,如果有兩個(gè)或更多的點(diǎn)具有最小y坐標(biāo)，就選最右的一個(gè)為p0

。很明顯，p0屬于凸包。ECNUYinpingLiu接著，所有點(diǎn)的坐標(biāo)被轉(zhuǎn)換為以p0為原點(diǎn)的坐標(biāo)，于是在S-{p0}中的點(diǎn)按照原點(diǎn)p0的極角排序，如果兩點(diǎn)pi和pj與p0形成同樣的極角，則更靠近p0的那一點(diǎn)排在前面。注意，在此我們無需計(jì)算從原點(diǎn)起的真實(shí)距離，因?yàn)榘ㄩ_方計(jì)算，計(jì)算它是耗費(fèi)很大的；這里我們只需要比較距離平方。設(shè)排序之后的表是T={p0，p1，…，pn-1}，其中p1

和pn-1分別與p0形成了最小和最大的極角。圖18.7顯示了一個(gè)按照關(guān)于p0的極角排序的13個(gè)點(diǎn)集合的例子。ECNUYinpingLiu現(xiàn)在，對(duì)事件點(diǎn)的進(jìn)度表，即排序表T開始掃描，掃描線的狀態(tài)用一個(gè)棧St

實(shí)現(xiàn)。棧初始時(shí)包含(pn-1，p0)，p0在棧頂。然后算法周游各點(diǎn)，從p1

開始到pn-1終止，在任何時(shí)刻，設(shè)棧的內(nèi)容是

St=(pn-1，p0，…，pi，pj)(pi和pj是最后壓人的點(diǎn))，并設(shè)pk是下一個(gè)考慮的點(diǎn)。如果三元組pi，pj，pk形成一個(gè)左旋，則pk壓人棧頂，同時(shí)掃描線移到下一個(gè)點(diǎn)；如果三元組pi，pj，pk

形成一個(gè)右旋或三點(diǎn)共線，則pj彈出棧，同時(shí)掃描線繼續(xù)留在pk。圖18．8顯示了在剛好處理完p5

后導(dǎo)出的凸包。這時(shí)，棧的內(nèi)容是(p12，p0，p1，p3，p4，p5)ECNUYinpingLiu圖18.8處理點(diǎn)p5后的凸包圖18.9處理點(diǎn)p6后的凸包在處理點(diǎn)p6之后，點(diǎn)p5，p4

和p3

相繼彈出棧，同時(shí)點(diǎn)p6壓入棧頂(見圖18.9)。最終的凸包在圖18.10中顯示。ECNUYinpingLiu圖18.10最終的凸包下面給出算法更形式的描述。在算法結(jié)束時(shí)，棧St

包含CH(S)的頂點(diǎn)，于是它可以轉(zhuǎn)化到鏈表中形成一個(gè)凸多邊形。算法18.3CONVEXHULL

輸入：平面上n個(gè)點(diǎn)的集合S。

輸出：CH(S)，存儲(chǔ)在棧St中的S的凸包。ECNUYinpingLiu1．設(shè)p0為具有最小

y坐標(biāo)的最右點(diǎn)2．T[0]←p03．設(shè)T[1…n-1]為S-{p0}中的點(diǎn)，按以p0為原點(diǎn)的極角的升序排列，如果兩個(gè)點(diǎn)pi和pj

以p0為原點(diǎn)有相同的極角，則與p0接近的那個(gè)點(diǎn)排在前面4．push(St，T[n一1])；push(St，T[0])5．k←16．whilek<n一17．設(shè)St=(T[n-1]，…，T[i]，T[j])，T[j]位于棧頂ECNUYinpingLiu8．IfT[i]，T[j]，T[k]為左旋

then9．push(St，T[k])10．k←k+111．elsepop(St)12．endif13．endwhile算法CONVEXHULL的運(yùn)行時(shí)間計(jì)算如下:ECNUYinpingLiu排序步驟耗費(fèi)O(nlogn)時(shí)間，至于while循環(huán)，我們觀察到，對(duì)于每一點(diǎn)恰好壓棧一次，最多彈棧一次。此外，檢驗(yàn)三點(diǎn)是否形成左旋或右旋相當(dāng)于計(jì)算它們帶符號(hào)的面積，耗時(shí)O(1)，這樣while循環(huán)的耗費(fèi)是O(n)?？梢娝惴ǖ臅r(shí)間復(fù)雜性是O(nlogn)。練習(xí)18．9給出了另一種方法，它可以避免計(jì)算極角，其他計(jì)算凸包的算法在練習(xí)18.10和練習(xí)18.13中概要敘述。5.計(jì)算點(diǎn)集的直徑ECNUYinpingLiu設(shè)S是平面中點(diǎn)的集合，我們定義S中任意兩點(diǎn)間的最大距離為S的直徑，記為Diam(S)。對(duì)于這個(gè)問題，一種直接的算法是比較每個(gè)點(diǎn)對(duì)的距離，返回S中兩點(diǎn)實(shí)現(xiàn)的最大距離。采用這一策略，我們將得到一個(gè)O(n2)時(shí)間的算法。在本節(jié)中，我們研究一種算法，它能在O(nlogn)時(shí)間內(nèi)找出平面中點(diǎn)集的直徑。我們從以下的觀察結(jié)論開始，它看起來是直觀的(見圖18.11)圖18.11ECNUYinpingLiu觀察結(jié)論18.1

一個(gè)點(diǎn)集的直徑是它的凸包的直徑,即Diam(S)=Diam(CH(S)).因此，要計(jì)算平面中點(diǎn)集的直徑，只需要考慮凸包上的頂點(diǎn)。所以下面將實(shí)際上考察尋找凸多邊形直徑的問題。定義18.3設(shè)P是一個(gè)凸多邊形，P的一條支撐線是指通過P頂點(diǎn)的一條直線l，它使得P的內(nèi)部整個(gè)地在l的一邊(見圖18.12)。ECNUYinpingLiu圖18.12凸多邊形的一些支撐線下面的定理中給出了凸多邊形直徑的一個(gè)有用的特性(見圖18.13)定理18.1

凸多邊形P的直徑等于P的任意平行支撐線對(duì)之間的最大距離。定義18.4.接納兩條平行支撐線的任意兩點(diǎn)稱為跖對(duì)。對(duì)于定理18.1，我們有如下推論:ECNUYinpingLiu圖18.13具有最大間隔的平行支撐線推論18.1

在凸多邊形中實(shí)現(xiàn)直徑的任何頂點(diǎn)對(duì)是一個(gè)跖對(duì)。根據(jù)上述推論，問題現(xiàn)在簡(jiǎn)化為找出所有的映對(duì)，并且選出具有最大間隔的那一對(duì)。事實(shí)上我們能夠以最優(yōu)線性時(shí)間完成。ECNUYinpingLiu定義18.5

定義點(diǎn)p和線段qr間的距離，記為dist(q,r,p),是從線段qr所在的直線到p的距離。如果dist(q,r,p)最大,則p是到線段qr

最遠(yuǎn)的點(diǎn)。考慮圖18.14(a),其中顯示了一個(gè)凸多邊形p。從該圖中我們很容易看到p5是離邊p12p1最遠(yuǎn)的頂點(diǎn)。類似地，頂點(diǎn)p9是離邊p1p2最遠(yuǎn)的頂點(diǎn)。(a)(b)圖18.14計(jì)算跖對(duì)ECNUYinpingLiu可以證明，一個(gè)頂點(diǎn)p和p1形成一個(gè)跖對(duì)當(dāng)且僅當(dāng)它是頂點(diǎn)p5，p6，…，p9的一個(gè)。一般地，對(duì)于某個(gè)m≤n，設(shè)點(diǎn)集凸包上的頂點(diǎn)按逆時(shí)針序是p1,p2,…,pm，當(dāng)沿逆時(shí)針方向掃過CH(S)的邊界時(shí)，設(shè)pl是第一個(gè)離邊p1p2最遠(yuǎn)的頂點(diǎn)(見圖18.14(b))。那么，在pk和pl間的任何頂點(diǎn)(包括pk和pl)和p1形成一個(gè)跖對(duì)。而且，所有其他頂點(diǎn)不和p1形成跖對(duì)。這個(gè)重要的觀察結(jié)論提示我們采用如下的方法來找出所有的跖對(duì).ECNUYinpingLiu首先從p2開始沿逆時(shí)針序掃過CH(S)的邊界直到我們找到pk，離pmp1最遠(yuǎn)的頂點(diǎn)。我們把點(diǎn)對(duì)(p1，pk)加到存放跖對(duì)且初始時(shí)為空的集合中去。然后我們繼續(xù)掃邊界并對(duì)于遇到的每一個(gè)頂點(diǎn)pi存放點(diǎn)對(duì)(p1，pj)，直到我們達(dá)到離p1p2最遠(yuǎn)的頂點(diǎn)Pl。可能有這樣的情況，l=k+1或甚至l=k，就是pl=pk。接著，我們進(jìn)到p2p3來尋找和p2形成跖對(duì)的頂點(diǎn)。這樣，我們同時(shí)做兩個(gè)邊界逆時(shí)針掃描：一個(gè)從p1到pk，另一個(gè)從pk到pm。當(dāng)探測(cè)到跖對(duì)(pk，pm)時(shí)掃描停止。最后，對(duì)跖對(duì)集合做一次線性掃描顯然足以找到凸包的直徑。由觀察結(jié)論18.1，它是所要求的點(diǎn)集的直徑。算法DIAMETER中給出了更形式的描述。ECNUYinpingLiu算法18.4DIAMETER

輸入：平面上n個(gè)點(diǎn)的集合S。

輸出：Diam(S)，S的直徑。

1．{P1，P2，