Parallelverarbeitung von Delaunay-Triangulationen und Voronoi-Diagrammen höherer Ordnung¹

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, Höhere Ordnung, Delaunay-Triangulation, Voronoi-Diagramm

Zusammenfassung

Delaunay-Triangulationen werden oft bei der Erstellung von Gitternetzen verwendet, da sie Dreiecke mit großen Winkeln garantieren. Es ist jedoch bei der Modellierung von Oberflächen möglich, daß die planare Delaunay-Triangulation Abweichungen von der Realität, sog. künstliche Dämme, verursacht. Zu deren Beseitigung ist von Gudmundsson et al. [21] das Konzept höherer Ordnungen bei Delaunay-Triangulationen eingeführt worden. Um dem Bedarf an Rechenleistung und Speicherkapazität der darauf aufbauenden Anwendungen wie Geographische Informationssysteme und Finite-Elemente-Methode gerecht zu werden, sind in dieser Arbeit optimale grobkörnige parallele Algorithmen im Kontext höherer Ordnungen entwickelt worden, die ausgehend von einer gewöhnlichen Delaunay-Triangulation eine Delaunay-Triangulation erster Ordnung, Voronoi-Diagramme beliebiger höherer Ordnungen und die Ordnung einer Triangulation berechnen.

Literaturverzeichnis

1

Agarwal, P. K.; de Berg, M; Matousek, J.; Schwarzkopf, O.: Constructing Levels in Arrangements and Higher Order Voronoi Diagrams. In: Proc. 10th Symp. on Computational Geometry (1994), S. 67-75.

2

Aggarwal, A.; Guibas, L. J.; Saxe, J.; Shor, P. W.: A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon. In: Discrete & Comput. Geometry 4 (1989), S. 591-604.

3

Akl, S.; Lyons, K.: Parallel Computational Geometry. Prentice Hall, 1993.

4

Aurenhammer, F.: A New Duality Result Concerning Voronoi Diagrams. In: Discrete & Computational Geometry 5 (1990), S. 243-254.

5

Aurenhammer, F.: Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Comput. Surv. 23 (1991), Nr. 3, S. 345-405.

6

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.

7

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.

8

Berg, M. de; Kreveld, M. J. van; Overmars, M.; Schwarzkopf, O.: Computational Geometry. Algorithms and Applications. 2. Aufl. Springer-Verlag, 2000.

9

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.

10

Boissonnat, J.-D.; Devillers, O.; Teillaud, M.: A Semi-Dynamic Construction of Higher Order Voronoi Diagrams and its Randomized Analysis. In: Algorithmica 9 (1993), S. 329-356.

11

Chan, T. M.: Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. SIAM J. Comput. 30 (2000), Nr. 2, S. 561-575.

12

Chazelle, B.; Edelsbrunner, H.: An Improved Algorithm for Constructing kth-Order Voronoi Diagrams. In: IEEE Transactions on Computers C-36 (1987), Nr. 11, S. 1349-1354.

13

Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.: Introduction to Algorithms. MIT Press, 1990.

14

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.

15

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.

16

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.

17

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.

18

Fortune, S.: A Sweepline Algorithm for Voronoi Diagrams. Algorithmica 2 (1987), S. 153-174.

19

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.

20

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.

21

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.

22

Gudmundsson, J.; Haverkort, H.; Kreveld, M. J. van: Constrained Higher Order Delaunay Triangulations. In: Proc. 19th Europ. Workshop on Comp. Geom. (2003), S. 105-108.

23

JaJa, J.: Introduction to Parallel Algorithms. Addison-Wesley, 1992.

24

Klein, R.: Algorithmische Geometrie. Addison-Wesley-Longman, 1997.

25

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.

26

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.

27

Lee, D.T.: On k-nearest neighbor Voronoi diagrams in the plane. In: IEEE Transactions on Computers 31 (1982), Nr. 6, S. 478-487.

28

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.

29

Meyerhenke, H.: Parallelverarbeitung spezieller Triangulationen. Diplomarbeit Friedrich-Schiller-Universität Jena. 2004.

30

Okabe, A.; Boots, B.; Sugihara, K.: Spatial tesselations. Concepts and applications of Voronoi diagrams. Wiley, 1992.

31

O'Rourke, J.: Computational Geometry in C. Cambridge University Press, 1994.

32

Preparata, F. P.; Shamos, M. I.: Computational Geometry - An Introduction. 2. Aufl., Springer-Verlag, 1988.

33

Ramos, E. A.: On range reporting, ray shooting and k-level construction. In: Proc. 15th Symp. on Computational Geometry (1999), S. 390-399.

34

Schaudt, B.: Higher Order Voronoi Diagrams: A Java Applet. Webseite abrufbar unter http://www.msi.umn.edu/~schaudt/voronoi/voronoi.html, Stand: April 1998, Abruf: 28.07.2004.

35

Valiant, L. G.: A Bridging Model for Parallel Computation. In: Communications of the ACM 33 (1990), Nr. 8, S.103-111.