支持空間分析的并行算法的研究與實(shí)現(xiàn).pdf

1、空間數(shù)據(jù)的復(fù)雜性會(huì)導(dǎo)致空間數(shù)據(jù)處理的延遲，這對(duì)實(shí)時(shí)性要求比較高的應(yīng)用問(wèn)題如軍事作戰(zhàn)等問(wèn)題產(chǎn)生了巨大的挑戰(zhàn)。設(shè)計(jì)支持空間分析的并行算法是解決此類問(wèn)題的有效方法，然而，目前國(guó)內(nèi)外對(duì)并行空間分析的算法研究卻很少。 本文的工作主要包括以下幾個(gè)方面： 1、采用平面掃描樹(shù)技術(shù)將平面掃描算法并行化。平面掃描樹(shù)技術(shù)可應(yīng)用于梯形分解，點(diǎn)定位等空間分析中，本文利用平面掃描樹(shù)技術(shù)進(jìn)行空間分析前先對(duì)一般的平面掃描樹(shù)進(jìn)行預(yù)處理，在樹(shù)的各結(jié)點(diǎn)中增

2、加一些指針和結(jié)構(gòu)，使得點(diǎn)定位的時(shí)間復(fù)雜度從O(log2n)降低到O(logn)。 2、采用分解歸并技術(shù)將平面掃描算法并行化。空間拓?fù)浞治鍪窃S多復(fù)雜空間分析算法的基礎(chǔ)，本文利用分解歸并的方法設(shè)計(jì)并實(shí)現(xiàn)了并行空間拓?fù)浞治鏊惴ā?3、許多空間分析算法都可歸結(jié)為凸包問(wèn)題的求解，本文改進(jìn)并實(shí)現(xiàn)了求取平面散亂點(diǎn)集凸包的并行算法，和已有并行算法相比，該算法設(shè)計(jì)更加簡(jiǎn)單，計(jì)算量更小。 4、本文的空間拓?fù)浞治鏊惴ㄊ且訰eal