同構化二維點集凸殼算法研究.pdf

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

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

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

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