一維可重構流水線總線并行機上計算幾何算法的設計.pdf

1、計算幾何是一門新興的學科,它在計算機圖形學、模式識別和地理數(shù)據(jù)庫等領域有著廣泛的應用.一維可重構流水線總線并行機是一種基于光通信技術的并行計算模型,它具有以往模型沒有的很多優(yōu)點,使得在它上面可以設計出一些非常快速又更易于實現(xiàn)的并行算法,所以在該模型上研究計算幾何算法具有重要的理論意義和實用價值.該文研究了LARPBS(a Linear Array with a Reconfigurable Pipelined Bus System)模型

2、上計算幾何中平面點集的凸殼、距離變換和單調(diào)多邊形的三角剖分等三個基本問題,分別提出了相應的并行算法.該文的主要內(nèi)容、貢獻和創(chuàng)新包括:(1)LARPBS上平面點集的凸殼算法提出分離的概念,并指出:兩個分離凸殼間的合并可通過并行計算點到凸殼的切線來完成,設計了兩分離凸殼間的合并算法,該算法具有直觀、簡明和高效的優(yōu)點.基于分治的思想,利用該算法,設計出凸殼算法.(2)LARPBS上任意維二值圖像的距離變換算法采用轉(zhuǎn)換的思想,使高維圖像的距離變

3、換問題簡化為求解若干個低維圖像的距離變換子問題,并設計了轉(zhuǎn)換算法.利用已有的LARPBS上二維圖像的距離變換算法,得到了任意維圖像的距離變換算法.(3)LARPBS上序列的最近較小(ANSV)算法提出匹配分割的概念,使問題簡化為合并有序序列和按序分布數(shù)據(jù).通過靈活拆分總線和合并子總線的方法動態(tài)重構光總線系統(tǒng),并巧妙利用光總線的消息播送技術,設計了數(shù)據(jù)移動算法.結(jié)合已有的合并有序序列的結(jié)論,提出了ANSV算法.(4)LARPBS上單調(diào)多邊