劉 萍

(甘肅民族師范學(xué)院，甘肅 合作 747000)

0 引言

本文討論平面點(diǎn)集的凸包的實(shí)時(shí)插入算法。假設(shè)平面點(diǎn)集S的點(diǎn)以數(shù)據(jù)流的方式進(jìn)入系統(tǒng)，如果對(duì)于已經(jīng)進(jìn)入系統(tǒng)的n個(gè)點(diǎn)的子集計(jì)算出它的凸包H，新的點(diǎn)P進(jìn)入系統(tǒng)時(shí)對(duì)H更新，更新的結(jié)果可能刪除P，或?qū)插入H，或?qū)插入H且刪除H的一些點(diǎn)，稱這種更新的算法為實(shí)時(shí)插入算法。本文提出的實(shí)時(shí)插入算法分為前向算法和后向算法。對(duì)于前向算法和后向算法，用算法所需的檢測次數(shù)為單位計(jì)算實(shí)時(shí)插入算法的復(fù)雜度。設(shè)S的點(diǎn)的個(gè)數(shù)是N，則計(jì)算凸包的實(shí)時(shí)算法所需的檢測次數(shù)小于3N，這個(gè)上界比起漸近復(fù)雜度更精確。

1 相關(guān)算法

1.1 凸包算法

S的凸包(或稱凸殼，convex hull)，是指包含S的所有凸集的交，或者說包含S的最小的凸集。凸包的計(jì)算起源于純幾何圖形的研究。由于在實(shí)際應(yīng)用中與幾何圖形有關(guān)的問題大量出現(xiàn)，如計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)CAD、建筑學(xué)等，從20世紀(jì)70年代起，利用計(jì)算機(jī)處理幾何圖形，越來越受到計(jì)算機(jī)科學(xué)界的重視。M.L.Shamos的博士論文[1]總結(jié)了上世紀(jì)70年代計(jì)算機(jī)科學(xué)家關(guān)于幾何圖形的算法研究，其中關(guān)于凸包的研究占據(jù)重要的位置。

平面有限點(diǎn)集S的凸包計(jì)算問題包括兩個(gè)方面:找出S的凸包多邊形的所有頂點(diǎn)(稱為S的極點(diǎn));將凸包多邊形的頂點(diǎn)按序(如逆時(shí)針順序)排列。找出極點(diǎn)的最簡單方法如下:

設(shè)P是點(diǎn)，如果存在S的不共線的3個(gè)點(diǎn)A、B、C，使得 P在△ABC的內(nèi)部3個(gè)角∠APB、∠BPC、∠CPA的和為2π，則P為S的內(nèi)點(diǎn);否則P是S的極點(diǎn)。因此，檢測的次數(shù)為O(n3)，其中n是S的點(diǎn)的個(gè)數(shù)。這樣，要找出S的所有極點(diǎn)的檢測次數(shù)為O(n4)。因?yàn)槠矫嬗邢撄c(diǎn)集S的極點(diǎn)的平均個(gè)數(shù)是O(logn)[2]，O(n4)的近似復(fù)雜度實(shí)在太大。在文獻(xiàn)[3]中，關(guān)于凸包計(jì)算的近似復(fù)雜度為O(n2)，這個(gè)結(jié)論使得凸包問題的研究向前跨越了很大的一步。實(shí)質(zhì)性的研究出現(xiàn)在1972年Graham的論文[4]，給出的復(fù)雜度為 O(nlogn)。以后，文獻(xiàn)[5]和文獻(xiàn)[6]，分別給出類似的結(jié)果(復(fù)雜度為 O(nlogn)和 O(nm)，m是極點(diǎn)的個(gè)數(shù))。

1.2 實(shí)時(shí)算法

文獻(xiàn)[7]和文獻(xiàn)[8]提出凸包問題的實(shí)時(shí)算法。在計(jì)算平面有限點(diǎn)集S的凸包的過程中，S的點(diǎn)經(jīng)常以數(shù)據(jù)流的方式進(jìn)入系統(tǒng)，而不是整個(gè)出現(xiàn)在系統(tǒng)中。以數(shù)據(jù)流的方式進(jìn)入系統(tǒng)的算法一般稱為實(shí)時(shí)算法。凸包問題的實(shí)時(shí)算法規(guī)定:當(dāng)S的第i個(gè)點(diǎn)p進(jìn)入系統(tǒng)時(shí)，先前進(jìn)入系統(tǒng)的i－1個(gè)點(diǎn)的子集的凸包Hi－1已經(jīng)計(jì)算出。實(shí)時(shí)算法需要計(jì)算 Hi－1∪{p}的凸包Hi。有3種可能:(1)p是Hi－1的內(nèi)點(diǎn)，因此Hi=Hi－1;(2)p 是 Hi－1的極點(diǎn)但不刪除 Hi－1的其它極點(diǎn)，因此 Hi=Hi－1∪{p};(3)p 是 Hi－1的極點(diǎn)且刪除Hi－1的某些極點(diǎn)。文獻(xiàn)[7]和文獻(xiàn)[8]的算法都是將Hi－1的點(diǎn)排成逆時(shí)針的順序，存儲(chǔ)在平衡樹(如AVL樹)中。在該樹中查找p在Hi－1的點(diǎn)的順序中的位置，通過各自的算法計(jì)算p和Hi－1的關(guān)系，都證明了計(jì)算時(shí)間為O(log m)，其中m是Hi－1的點(diǎn)的個(gè)數(shù)。

2 插入算法

2.1 Graham掃描算法

設(shè)S是平面上有n個(gè)點(diǎn)的點(diǎn)集，文獻(xiàn)[4]選取S中的3個(gè)不共線的點(diǎn)組成的三角形的重心P0作為基點(diǎn)?；c(diǎn)P0的選取可以在O(n)時(shí)間完成。Efron在文獻(xiàn)[9]中證明，如果S是絕對(duì)連續(xù)分布，則任選三點(diǎn)必以概率1保證三點(diǎn)不共線，因此，上述時(shí)間為O(1)。P0與S的點(diǎn)P組成的向量P0P與正X軸的夾角記為θ(P)，將 S的 P按 θ(P)的升序排列為 P1，…，Pn。在文獻(xiàn)[10]和文獻(xiàn)[11]中基點(diǎn)選取 S中縱坐標(biāo)最小的點(diǎn)，這樣做的好處是上述的夾角不超過π，但對(duì)于下文的插入算法，不取這種點(diǎn)。令 P0=Pn+1，Graham掃描算法從 i=0起，計(jì)算3個(gè)點(diǎn) Pi、Pi+1、Pi+2的旋轉(zhuǎn)順序，如果為左旋，則計(jì)算 Pi+1、Pi+2、Pi+3，否則丟棄 Pi+1，退回計(jì)算 Pi－1、Pi+2、Pi+3。算法結(jié)束時(shí)，輸出按逆時(shí)針方向排序的凸包頂點(diǎn)。掃描算法的檢測次數(shù)不超過2n，θ(P)的排列時(shí)間為 O(nlogn)。

2.2 簡單的結(jié)論

設(shè)A、B、C是平面上的3個(gè)點(diǎn)，對(duì)A、B、C所作的檢測是指:如果A、B、C按逆時(shí)針(順時(shí)針)方向排列，則稱 A、B、C為左(右)旋。設(shè) A、B、C的坐標(biāo)是(xi，yi)(i=1，2，3)，則 A、B、C 左旋(右旋)當(dāng)且僅當(dāng)(x2－x1)(y3－y1)－(x3－x1)(y2－y1)＞0(＜0)。設(shè)A、B是直線L上兩點(diǎn)，點(diǎn)C、D稱為在L的同側(cè)，如果A、B、C和A、B、D同時(shí)為左旋或者同時(shí)為右旋。下面的結(jié)論是顯然的。

引理 設(shè)S是平面點(diǎn)集。(1)設(shè)P∈S。P是S的極點(diǎn)當(dāng)且僅當(dāng)存在過P的直線L使得S的點(diǎn)(除去P)都在L的同側(cè)。(2)若P、R是S的極點(diǎn)，則S的點(diǎn)(除去P，R)都在L的同側(cè)。

2.3 插入算法

設(shè)S是平面有限點(diǎn)集，H是按Graham算法計(jì)算得到的S的凸包，按逆時(shí)針排序，H={P1，…，Pn}，P0是基點(diǎn)。設(shè)Q是插入點(diǎn)，S1=H∪{Q，P0}，H1是S1的凸包。計(jì)算H1的插入算法如下。

輸入 凸包H，插入點(diǎn)Q。

輸出 S1=H∪{Q，P0}的凸包H1。

Step1 在O(logn)時(shí)間內(nèi)找到i使得θ(Pi)≤θ(Q)＜θ(Pi+1)。

Step2 如果PiQPi+1右旋，H1=H，算法中止。

Step3 如果PiQPi+1左旋，H1←H∪{Q}，

Step3.1 前向算法:

(1)k=i;

(2)若Pk－1PkQ左旋，前向算法終止;

(3)若 Pk－1PkQ 右旋，H1←H1－{Pk}，k －－ ，返回Step2。

Step3.2 后向算法:

(1)k=i+1;

(2)若QPkPk+1左旋，后向算法終止;

(3)若 QPkPk+1右旋，H1←H1－{Pk}，k++，返回Step2。

Step4 輸出H1。

2.4 插入算法正確性的證明

設(shè)H1是2.3節(jié)插入算法輸出的點(diǎn)集，需要證明H1是S1的凸包。根據(jù)算法，如果PiQPi+1右旋，則Q和P0在直線PiPi+1的同側(cè)，因此Q是S1的內(nèi)點(diǎn)，所以H1=H。否則，如果PiQPi+1左旋，將Q插入H，執(zhí)行前向算法和后向算法。若前向算法在k=h終止，后向算法在k=m中止，則Ph+1，…，Pi以及Pi+1，…，Pm－1都不是極點(diǎn)，從 H1中刪除，H1={P1…PhQPm…Pn}。因?yàn)镠是凸包，因此所有PsPs+1Ps+2(s=0，…，h－2，m，…，n－1)都是左旋，因此，所有 Pj(j=1，…，h，m，…，n)都是極點(diǎn)。剩下只需證明Q是極點(diǎn)。因?yàn)镻iQPi+1左旋，因此Q和P0在直線PiPi+1的兩側(cè)，而P0和H的點(diǎn)在直線PiPi+1的同側(cè)。過Q作直線L平行PiPi+1，則H1的點(diǎn)(除去Q)都在L的同側(cè)，因此Q是極點(diǎn)。

2.5 插入算法的效率

在2.3節(jié)的算法中，關(guān)于左右旋的檢測次數(shù)最好的情形是一次(Q不是極點(diǎn))，或3次(Q是極點(diǎn)且不刪除其他點(diǎn))，最壞的情形是n+1次，即Q是極點(diǎn)且刪除所有Pi(i=2，…，n－1)。如果刪除的點(diǎn)越多，剩下的點(diǎn)也就越少，有利于下次插入。因此，提出用插入算法來計(jì)算凸包。

3 凸包計(jì)算的實(shí)時(shí)插入算法

設(shè)S是平面上有N個(gè)點(diǎn)的集合，S的點(diǎn)順序進(jìn)入系統(tǒng)。下面的定理給出應(yīng)用實(shí)時(shí)插入算法所需要的檢測次數(shù)的上界。

定理 計(jì)算平面點(diǎn)集S的凸包實(shí)時(shí)插入算法所需的檢測次數(shù)小于3N(N是S的點(diǎn)的個(gè)數(shù))。

證明 首先計(jì)算進(jìn)入系統(tǒng)的t個(gè)點(diǎn)(t是較小的數(shù))的子集的凸包H。計(jì)算H的時(shí)間是和N無關(guān)的常數(shù)C。以后進(jìn)入系統(tǒng)的點(diǎn)按2.3節(jié)的算法更新H。設(shè)H的點(diǎn)的個(gè)數(shù)是n。當(dāng)?shù)趇個(gè)點(diǎn)P進(jìn)入系統(tǒng)，需要作一次檢測。如果P是內(nèi)點(diǎn)，H的點(diǎn)的個(gè)數(shù)不變，轉(zhuǎn)向下一個(gè)點(diǎn)。如果P不是內(nèi)點(diǎn)，進(jìn)入系統(tǒng)后利用前向算法刪除H的h個(gè)點(diǎn)，檢測次數(shù)為h+1，利用后向算法刪除H的m個(gè)點(diǎn)，檢測次數(shù)為m+1(h，m≥0)，則需要完成的檢測次數(shù)為u=1+h+1+m+1=h+m+3。因?yàn)镠的點(diǎn)被刪除h+m個(gè)，因此H的點(diǎn)的個(gè)數(shù)為n－h(huán)－m。當(dāng)S的k個(gè)點(diǎn)進(jìn)入系統(tǒng)，分別檢測u1，…，uk次，ui=hi+mi+3。則 k個(gè)點(diǎn)進(jìn)入系統(tǒng)的檢測次數(shù)T=u1+…+uk，則H的點(diǎn)被刪除的個(gè)數(shù)是T－3k。因此H的個(gè)數(shù)為n－T+3k。如果S有N個(gè)點(diǎn)，則k=N－n。因?yàn)镠的點(diǎn)的個(gè)數(shù)大于0，因此n－T+3(N－n)＞0，即T＜3N。這就保證，利用實(shí)時(shí)算法計(jì)算有N個(gè)點(diǎn)的平面點(diǎn)集S的凸包所需的檢測次數(shù)小于3N。

4 結(jié)束語

凸包計(jì)算的研究有著廣泛的應(yīng)用背景。本文在Graham掃描算法的基礎(chǔ)上，提出前向算法和后向算法。一般的凸包計(jì)算的復(fù)雜度如在第1節(jié)中指出的結(jié)論都是漸近公式，如O(NlogN)和O(mN)(N是集合S的元素個(gè)數(shù)，m是凸包的點(diǎn)的個(gè)數(shù))。在本文的結(jié)論中，得到精確的上界3N。此外，在本文的算法中，不需要Graham掃描算法中必須的排序工作(時(shí)間O(NlogN))。因?yàn)樵谒惴ǖ牡?步中，為了找到i的位置所需的時(shí)間只是O(logm)。

[1]Shamos M I.Computational Geometry[D].Department of Computer Science，Yale University，1978.

[2]Bentley J L，Kung H T，Schkolnick M，et al.On the average number of maxima in a set of vertors and applications[J].Journal of the Association for Computing Machinery，1978，25(4):536-543.

[3]Chand D R，Kapur S S.An algorithm for convex polytopes[J].Journal of the ACM，1970，17(1):78-86.

[4]Graham R L.An efficient algorithm for determining the convex hull of a finite planar set[J].Information Processing Letter，1972，1(4):132-133.

[5]Javis R A.On the identification of the convex hull of a finite set of points in the plane[J].Information Processing Letter，1973，2(1):18-21.

[6]Shamos M I.Germetric complexity[C]//Proceedings of the 7th Annual ACM Symposium on Theory of Computing.1975:224-233.

[7]Preparata F T.An optimal real-time algorithm for planar convex hulls[J].Communication of ACM，1979，22(7):402-405.

[8]周之英.平面點(diǎn)集凸殼的實(shí)時(shí)算法[J].計(jì)算機(jī)學(xué)報(bào)，1985，8(2):136-142.

[9]Efron B.The convex hull of a randon set of points[J].Blometrika，1965，52(3):331-343.

[10]霍羅威茨.計(jì)算機(jī)算法[M].馮博琴，等譯.北京:機(jī)械工業(yè)出版社，2005.

[11]鄭宗漢，鄭曉明.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社，2005.

[12]Bronnimann H，Iacono J，et al.Space-efficient planar convex hull algorithms[J].Theoretical Computer Science，2004，321(1):25-40.

[13]周培德，付夢印.尋求簡單多變形凸殼的線性時(shí)間算法[J].計(jì)算機(jī)工程與科學(xué)，2002，24(3):1-2，44.

[14]金文華，何濤，等.基于有序簡單多邊形的平面點(diǎn)集凸包快速求取算法[J].計(jì)算機(jī)學(xué)報(bào)，1998，21(6):533-539.