一維可重構(gòu)流水線總線并行機(jī)上計算幾何算法的設(shè)計.pdf

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

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

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