Delaunay-Triangulation und Tiefensortierung auf grobkörnigen Parallelrechnern1

Henning Meyerhenke, Hans-Dietrich Hecker

Fakultät für Mathematik und Informatik
Institut für Informatik
Friedrich-Schiller-Universität Jena


E-Mail: henning (AT) meyerhenke.de, hdh (AT) minet.uni-jena.de



Stichwörter

Parallele Algorithmische Geometrie, Delaunay-Triangulation, TIN-Algorithmen, Parallele Tiefensortierung



Zusammenfassung

Die Delaunay-Triangulation wird oft bei der Erstellung von Dreiecksnetzen (TINs) verwendet, da sie Dreiecke mit großen Winkeln garantiert. Um dem Bedarf an Rechenleistung und Speicherkapazität der darauf aufbauenden Anwendungen wie Geographische Informationssysteme und Finite-Elemente-Methode gerecht zu werden, werden in dieser Arbeit deterministische grobkörnige parallele Algorithmen zur Berechnung der planaren Delaunay-Triangulation und zur Tiefensortierung von Dreiecken eines geeigneten TINs entworfen. Der Delaunay-Algorithmus arbeitet als erstes deterministisches Verfahren mit optimaler lokaler Berechnungskomplexität im CGM-Modell, zumindest für viele Punktverteilungen.



Literaturverzeichnis

1
Akl, S.; Lyons, K.: Parallel Computational Geometry. Prentice Hall, 1993.
2
Amato, N. M.; Goodrich, M. T., Ramos, E. A.: Parallel algorithms for higher-dimensional convex hulls. In: Proc. 35th Annual IEEE Symp. on Foundations of Computer Science (1994), S. 683-694.
3
Aurenhammer, F.: A New Duality Result Concerning Voronoi Diagrams. In: Discrete & Computational Geometry 5 (1990), S. 243-254.
4
Aurenhammer, F.: Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Comput. Surv. 23 (1991), Nr. 3, S. 345-405.
5
Aurenhammer, F.; Klein, R.: Voronoi Diagrams. In: Handbook of Computational Geometry. Hg. von J.-R. Sack u. J. Urrutia. Elsevier Science, 1999. S. 201-290.
6
Aurenhammer, F.; Schwarzkopf, O.: A Simple On-Line Randomized Incremental Algorithm for Computing Higher Order Voronoi Diagrams. In: Proc. 7th Symp. on Computational Geometry (1991), S. 142-151.
7
Aurenhammer, F.; Xu, Y.-F.: Optimal triangulations. In: Encyclopedia of Optimization, Bd. 4. Hg. von P. M. Pardalos u. C. A. Floudas. Kluwer Academic Publishing, 2000. S. 160-166.
8
Bäumker, A.; Dittrich, W.; Meyer auf der Heide, F.: Truly Efficient Parallel Algorithms: c-Optimal Multisearch for an Extension of the BSP Model. In: Proc. 3rd ESA (1995), S. 17-30.
9
Berg, M. de: Visualization of TINs. In: Algorithmic Foundations of Geographic Information Systems. Lecture Notes in Computer Science 1340. Hg. von M. J. van Kreveld, J. Nievergelt, T. Roos u. P. Widmayer. Springer-Verlag, 1997. S. 79-97.
10
Berg, M. de; Kreveld, M. J. van; Overmars, M.; Schwarzkopf, O.: Computational Geometry. Algorithms and Applications. 2. Aufl. Springer-Verlag, 2000.
11
Bern M.; Eppstein, D.: Mesh Generation And Optimal Triangulation. In: Computing in Euclidean Geometry. 2. Aufl. Hg. von D.-Z. Du u. F. Hwang. World Scientific, 1995. S. 47-123.
12
Blelloch, G. E.; Hardwick, J. C.; Miller, G. L.; Talmor, D.: Design and Implementation of a Practical Parallel Delaunay Algorithm. In: Algorithmica 24 (1999), S. 243-269.
13
Brouns, G.; Wulf, A. de; Constales, D.: Multibean data processing: Adding and deleting vertices in a Delaunay triangulation. In: The Hydrographic Journal 101 (2001), S. 3-9.
14
Chin, F.; Wang, C. A.: Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time. SIAM J. Comput. 28 (1998), Nr. 2, S. 471-486.
15
Cignoni, P.; Montani, C.; Perego, R.; Scopigno, R.: Parallel 3D Delaunay Triangulation. Comput. Graph. Forum 12 (1993), Nr. 3, S. 129-142.
16
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.: Introduction to Algorithms. MIT Press, 1990.
17
Dehne, F.; Deng, X.; Dymond, P.; Fabri, A.; Khokhar, A. A.: A Randomized Parallel Three-Dimensional Convex Hull Algorithm for Coarse-Grained Multicomputers. In: Theory of Computing Systems 30 (1997), Nr. 6, S. 547-558.
18
Dehne, F.; Fabri, A.; Rau-Chaplin, A.: Scalable parallel geometric algorithms for coarse grained multicomputers. In: Proc. 9th Symp. on Computational geometry (1993), S. 298-307.
19
Dehne, F.; Fabri, A.; Rau-Chaplin, A.: Scalable parallel computational geometry for coarse grained multicomputers. In: Int. J. Comput. Geometry 6 (1996), Nr. 3, S. 379-400.
20
Diallo, M.; Ferreira, A.; Rau-Chaplin, A.: A Note On Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram. In: Parallel Processing Letters 11 (2001), Nr. 2-3, S. 327-340.
21
Dwyer, R. A.: A Faster Divide-and-Conquer Algorithm for Constructing Delaunay Triangulations. In: Algorithmica 2 (1987), S. 137-151.
22
Fortune, S.: A Sweepline Algorithm for Voronoi Diagrams. Algorithmica 2 (1987), S. 153-174.
23
Fortune, S.: Voronoi Diagrams and Delaunay Triangulations. In: Euclidean Geometry and Computers. Hg. von D. A. Du u. F. K. Hwang. World Scientific Publishing, 1992. S. 193-233.
24
Fortune, S.: Voronoi Diagrams and Delaunay Triangulations. In: Handbook of Discrete and Computational Geometry. Hg. von J. O'Rourke u. J. E. Goodman. CRC Press, 1997. S. 377-388.
25
Goodrich, M. T.: Communication-Efficient Parallel Sorting. In: SIAM J. on Computing 29 (1999), Nr. 2, S. 416-432.
26
Graham, R. L.: An Efficient Algorithm For Determining the Convex Hull of a Planar Set. In: Information Processing Letters 1 (1972), Nr. 4, S. 132-133.
27
Gudmundsson, J.; Hammar, M.; Kreveld, M. J. van: Higher Order Delaunay Triangulations. In: Computational Geometry - Theory and Appl. 23 (2002), Nr. 1, S. 85-98.
28
Guibas, L.; Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of Voronoi Diagrams. In: ACM Transactions on Graphics 4 (1985), Nr. 2, S. 74-123.
29
JaJa, J.: Introduction to Parallel Algorithms. Addison-Wesley, 1992.
30
Klein, R.: Algorithmische Geometrie. Addison-Wesley-Longman, 1997.
31
Kreveld, M. J. van: Digital Elevation Models and TIN Algorithms. In: Algorithmic Foundations of Geographic Information Systems. Lecture Notes in Computer Science 1340. Hg. von M. J. van Kreveld, J. Nievergelt, T. Roos u. P. Widmayer. Springer-Verlag, 1997. S. 37-78.
32
Kühn, U.: Lokale Eigenschaften in der algorithmischen Geometrie mit Anwendungen in der Parallelverarbeitung. Dissertation Westfälische Wilhelms-Universität Münster. 1998. 116 S.
33
Lee, S.; Park, C.-I.; Park, C.-M.: An Improved Parallel Algorithm for Delaunay Triangulation on Distributed Memory Parallel Computers. In: Parallel Processing Letters 11 (2001), Nr. 2/3, S. 341-352.
34
Mehlhorn, K.; Näher, S.: LEDA. A platform for combinatorial and geometric computing. Cambridge University Press, 1999.
35
Mulmuley, K.; Schwarzkopf, O.: Randomized Algorithms. In: Handbook of Discrete and Computational Geometry. Hg. von J. O'Rourke u. J. E. Goodman. CRC Press, 1997. S. 633-652.
36
Okabe, A.; Boots, B.; Sugihara, K.: Spatial tesselations. Concepts and applications of Voronoi diagrams. Wiley, 1992.
37
O'Rourke, J.: Computational Geometry in C. Cambridge University Press, 1994.
38
Preparata, F. P.; Shamos, M. I.: Computational Geometry - An Introduction. 2. Aufl., Springer-Verlag, 1988.
39
Seidel, R.: Convex hull computations. In: Handbook of Discrete and Computational Geometry. Hg. von J. O'Rourke u. J. E. Goodman. CRC Press, 1997. S. 361-375.
40
Shi, H.; Schaeffer, J.: Parallel sorting by regular sampling. In: Journal of Parallel and Distributed Computing 14 (1992), Nr. 4, S. 361-372.
41
Snir, M.; Otto, S.; Huss-Lederman, S.; Walker, D.; Dongarra, J.: MPI: The Complete Reference. Bd. 1, 2. Aufl. MIT Press, 1998.
42
Spencer, T. H.: Time-Work Tradeoffs for Parallel Algorithms. In: Journal of the ACM 44 (1997), Nr. 5, S. 742-778.
43
Su, P.; Drysdale, R. L. S.: A Comparison of Sequential Delaunay Triangulation Algorithms. In: Proc. 11th Annual Symp. on Computational Geometry (1995), S. 61-70.
44
Valiant, L. G.: General Purpose Parallel Architectures. In: Handbook of Theoretical Computer Science, Bd. A: Algorithms and Complexity. Hg. von J. van Leeuwen. Elsevier and MIT Press, 1990. S. 943-972.
45
Valiant, L. G.: A Bridging Model for Parallel Computation. In: Communications of the ACM 33 (1990), Nr. 8, S.103-111.
46
Weiss, M. A.: Data Structures and Algorithm Analysis in C++. 2. Aufl. Addison-Wesley, 1999.



1Diese Arbeit enthält Teilergebnisse der Diplomarbeit des ersten Verfassers, die unter Betreuung des zweiten Verfassers angefertigt wurde.