Dissertation > Excellent graduate degree dissertation topics show

Research and Implementation of Limited Voronoi Diagram Generation Based on Multi-Core Environment

Author: WuZuo
Tutor: DongLanFang
School: University of Science and Technology of China
Course: Theory of computer software
Keywords: Computational geometry limited Voronoi Delaunay triangulation divide and conquer algorithm parallel computing MPI language heterogeneous multi-core
CLC: TP391.41
Type: Master's thesis
Year: 2010
Downloads: 124
Quote: 1
Read: Download Dissertation

Abstract


As a basic data structure element of discrete space division, Voronoi mesh is an important research direction in the field of computational geometry. Because of the characteristic of perpendicular bisector, Voronoi mesh especially suitable for solving some physical problems related to conservation nature by the method of finite volume, such as fluid flow, heat conduction and so on. However, in these application areas, the generation of the Voronoi diagram has a special qualification, take the example of reservoir simulation, the Voronoi mesh can not cross some physical barriers, like the border and faults. For some particular points, such as horizontal well and vertical well must be the center of the Voronoi mesh. Consider the requirement of constructing limited Voronoi mesh in some practical applications and the problem of constructing high-quality Voronoi mesh under the complex constrained conditions through large-scale data processing, research and implementation of limited Voronoi mesh generation and its parallel algorithms is necessary.Under the computing ability of single-core, using large-scale data to generate limited Voronoi mesh is low efficiency and its calculation time can not be accepted, however, using the large-scale parallel processor for data processing needs high cost, and it’s not convenient to operation. With the rapid development of hardware and processor, heterogeneous multi-core has become the main trend of high performance computing. In this paper, we present a available and efficient Voronoi mesh generation parallel algorithm by using MPI parallel programming language under the environment of multi-core, the specific research and content as the follows:(1) Implementation the algorithm of Constructing Voronoi mesh by the indirect method, which is high-quality but low efficiency.(2) Consider the parallel algorithm, we use the optimal algorithm of divide and conquer to achieve limited Voronoi mesh generation. According to the two qualifications (the principles of limited point and limited line), we make analysis and processing on each limited situation, which is prepare for constructing high-quality mesh generation latter. (3) Constructing limited Voronoi mesh of large-scale point set by optimal algorithm-Divide and Conquer alrgorithm, we also design and modify the parallel data structure-doubly-connected edge list, which is easy to conform parallel processing and complex features of complex limited boundary.(4) Using MPI and C programming language, according to the gradually merge in the whole parallel program, we do the parallel processing of reasonable distribution of point and constructing limited Voronoi mesh generation. We run the program under the environment of on the HP large-scale parallel machine and heterogeneous multi-core machine, and get its experimental results.(5) Achieve the Voronoi diagram transform to its dual diagram-Delaunay diagram, and realize real-time graphics display by ultimate data processing.Based on the content of this paper, we can apply our research results on the fields of fluid flow simulation, modeling drawing and so on. Combined with multi-core processors and the rapid development of parallel computing, we can use this parallel algorithm to solve many problems of real-time computing related to simulation. Finally, the future research direction of Voronoi diagram is presented.

Related Dissertations

  1. The Airborne LiDAR and LiDAR Points-cloud’s Quick Processing Method,TN959.73
  2. The Research on Feature Selection for Data Stream,TP311.13
  3. Research on Detecting and Tracking of Fish Group Based on Machine Vision,TP391.41
  4. The Algorithm Researches of Novel Wide Area Backup Protection for Power Grid,TM774
  5. The Research on Online Adaptive Settings,TM77
  6. OSG-based three-dimensional irregular terrain matching military standard applied research,E919
  7. Image retrieval method and system for parallel computing,TP391.3
  8. Research of Digital Elevation Model Generation and Visualization Based on TIN,TP391.41
  9. EFI-based software model of heterogeneous multi-core systems and its security applications,TP316
  10. Cooling Turbine Blade CFD Grid Generation,V232.4
  11. The Mechanism Research of Visualization Experiment Approach for Solving System Global Shortest Path,TP13
  12. Key Technology Research of Block Modeling in Seismic Imaging System,TP391.41
  13. System design and application of a two-dimensional grid Automeshening,TP391.41
  14. The Primary Research for Flow Simulation on Unstructured Grids,O35
  15. The Study on the Computing System of Relay Coordination for Extra-High Voltage Power Grid Based on .NET Platform,TM774
  16. Research on the Surface REconstruction Based on Geometric Shapes,TP391.7
  17. The Research on Carving Surface Modeling Based on Planar Random Closed Graph,TP391.72
  18. Study on Improved Fingerprint Identification Algorithm Based on Delaunay Triangulation,TP391.41
  19. The Design and Implementation of a Distributed Storage and Retrieval System,TP333
  20. Design and Implementation of Doppler Weather Radar Data Analysis System,TN959.4
  21. Design and Simulation of a Topology Control Algorithm for Ad Hoc Networks,TN929.5

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Pattern Recognition and devices > Image recognition device
© 2012 www.DissertationTopic.Net  Mobile