同構(gòu)化二維點(diǎn)集凸殼算法研究.pdf

1、凸殼問題是計(jì)算幾何中最重要、最基本，也是得到大量深入研究，并有廣泛應(yīng)用的問題之一。其應(yīng)用領(lǐng)域包括統(tǒng)計(jì)學(xué)等。它是在20世紀(jì)提出的，70年代以來，二維凸殼所具有的問題復(fù)雜性與應(yīng)用重要性，使國內(nèi)外專家學(xué)者對凸殼算法頗為關(guān)注，20世紀(jì)末期就已提出很多著名的凸殼算法，諸如卷包裹凸殼算法、格雷厄姆凸殼算法、折半分治凸殼算法，等等<'[5]>?？梢哉f凸殼算法研究始于70年代、盛于80年代、極于90年代；然而，進(jìn)入21世紀(jì)以來，凸殼算法研究出現(xiàn)了停滯不

2、前的尷尬窘?jīng)r，所以有關(guān)凸殼的生成算法不是很多。在現(xiàn)有的凸殼算法里不但有串行并行之分，同時(shí)亦有“增點(diǎn)”遞推與“刪點(diǎn)”遞推之分。 本文在前人研究的基礎(chǔ)上，展開了基于同構(gòu)化基本原理新視角的點(diǎn)集凸殼算法(注：包括串行算法與并行算法；下同)研究。同構(gòu)化點(diǎn)集凸殼算法研究的主要內(nèi)容有： (1)現(xiàn)行點(diǎn)集凸殼算法反思研究，以發(fā)掘其弱點(diǎn)根源、借鑒其歷史經(jīng)驗(yàn)； (2)點(diǎn)集凸殼的同構(gòu)化構(gòu)造特性研究，以尋求其同構(gòu)化構(gòu)造本質(zhì)； (3

3、)點(diǎn)集凸殼算法同構(gòu)化研究，以創(chuàng)出性能更優(yōu)的點(diǎn)集凸殼新算法。 在同構(gòu)化研究的基礎(chǔ)之上，本文提出了具有代表性的“動態(tài)基線最大傾角的凸殼新算法”、“雙域雙向水平傾角最小化圈繞凸殼新算法”、和“基于工作站機(jī)群的并行凸殼新算法”，并且利用任一電子商務(wù)的文檔，必定的能唯一標(biāo)識它的特性——“文紋”，首次將凸殼技術(shù)運(yùn)用于數(shù)字加密，提出了“基于文紋的數(shù)字加密技術(shù)”。 除了以上用途外，凸殼在“計(jì)算圖形、圖象處理、模式識別、指紋識別、地物辨識

4、、地質(zhì)勘探、網(wǎng)點(diǎn)布局、環(huán)境監(jiān)測、……”中，均有廣泛而重要的學(xué)術(shù)意義與應(yīng)用價(jià)值。例如：圖象處理中，可用尋求圖像凸殼，找到數(shù)字圖象中的關(guān)鍵凸面；古繁體文字分解中，可以構(gòu)造字形凸包，形成對文字的最優(yōu)劃分；模式識別中，可借模式凸殼，描述模式外形的重要特征；物體分類中，可憑各物體凸殼相似度，勾畫出這些物體所屬類別；計(jì)算機(jī)圖形學(xué)中，可用一組點(diǎn)的凸殼，顯示出其點(diǎn)簇：在指紋識別中，可以根據(jù)指紋邊緣輪廓點(diǎn)集凸殼，獲得高質(zhì)量的指紋，所以說凸殼的應(yīng)用范圍非常