A parallel strategy for plane sweep algorithm in multi-core system

This paper proposes to design and realize a parallel strategy based on plane sweep algorithm that can be used in the multi-core system. The main contribution of this work is to present an efficient method to compute the large and complex data with plane sweep method. We use MPI (Message Passing Interface) as the programming model in Linux multi-core system, select shape file as the standard input and output files, and present a dynamic tree merge model to collect the result from each computing core, in which the time complexity can be reduced from O(n²) to O(n log n) and the problem of data lock and load balancing can be effectively solved. Experiment shows that in single-core system, our algorithm has a better performance than ArcGIS; in multi-core system of 8-cores, our algorithm can obtain 8× speedups compared with ArcGIS.