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

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

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

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