Research And Realization Of Parallel Algorithm Supporting Spatial Analysis

The spatial data's complexity leads to the delay of spatial data processing, which has made great challenges to the fields which have high real-time requirements. It is an efficient way to design the parallel algorithms which support spatial analysis to solve these problems. However, at present, there is only a small number of researches for parallel spatial analysis.The works this disseration mainly include are as follows:1. Using the plane-sweep tree technique to make the plane-sweep algorithm parallelization. The plane-sweep tree technique can be applied to Trapezoidal Decomposition, Planner Point Location ,and so on.This dissertation firstly preprosesses the general plane-sweep tree by adding some sets and pointers to the nodes,and then makes the special spatial analysis.This way makes the time complexity of the point location problem reduce from O(log2n) to O(logn).2. Using the divide–and-merge technique to make the plane-sweep algorithm parallization. Spatial topological analysis is the basis of many complex spatial problems. This dissertation uses the divide-and-merge technique to design and realize the parallel spatial topological analysis.3. Many spatial analysis algorithms are all based on the convex problem.This dissertation improves and realizes parallel convex hull algorithm for planner point set.Comparing the existing algorithms , the algorithm in this dissertation is simpler in designing , and has less computation.4. The spatial topological algorithms of this dissertation design and organize the data based on Realms.Comparing to spatial analysis based on Euclidean Space, Realms is able to make the spatial analysis localization, which greatly convenients the realization of parallel algorithms.