Parallele Algorithmische Geometrie anhand von Delaunay-Triangulationen¹

Henning Meyerhenke und Hans-Dietrich Hecker

Abstract:

Delaunay-Triangulationen werden oft bei der Erstellung von Dreiecksnetzen (TINs) verwendet, da sie Dreiecke mit großen Winkeln garantieren. Um den Bedarf an Rechenleistung und Speicherkapazität der darauf aufbauenden Anwendungen wie Geographische Informationssysteme und Finite-Elemente-Methode gerecht zu werden, werden die Programme, die diese Datenstruktur nutzen, meist auf Parallelrechnern ausgeführt. Um die Ausführung dieser Programme möglichst effizient zu gestalten, muß auch die Delaunay-Triangulation parallel konstruiert werden. Diese Arbeit stellt daher bekannte serielle und parallele Algorithmen zur Berechnung der Delaunay-Triangulation einer planaren Punktmenge sowie verschiedene Modelle für den parallelen Algorithmenentwurf vor. Sowohl Verfahren als auch Modelle werden verglichen und hinsichtlich theoretischer und praktischer Qualitäten beurteilt.

Bibliography

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

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.

5

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

6

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

7

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.

8

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.

9

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.

10

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.

11

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.

12

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

13

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.

14

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.

15

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.

16

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.

17

Chan, T. M.: Output-sensitive results on convex hulls, extreme points, and related problems. In: Proc. 11th Symp. on Computational Geometry (1995), S. 10-19.

18

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.

19

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.

20

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.

21

Cignoni, P.; Montani, C.; Perego, R.; Scopigno, R.: Parallel 3D Delaunay Triangulation. Comput. Graph. Forum 12 (1993), Nr. 3, S. 129-142.

22

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

23

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.

24

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.

25

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.

26

Delaunay, B.: Sur la sphre vide. A la memoire de Georges Voronoi. In: Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk 7 (1934), S. 793-800. Literaturverweis nach Aurenhammer und Klein [7].

27

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.

28

Diallo, M.; Ferreira, A.; Rau-Chaplin, A.; Ubéda, S.: Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained Multicomputers. In: J. Parallel Distrib. Comput. 56 (1999), Nr. 1, S. 47-70.

29

Dwyer, R. A.: A Faster Divide-and-Conquer Algorithm for Constructing Delaunay Triangulations. In: Algorithmica 2 (1987), S. 137-151.

30

Estivill-Castro, V.; Lee, I.: AMOEBA: Hierarchical Clustering Based on Spatial Proximity Using Delaunay Triangulation. Techn. Bericht 99-05 (1999), Dep. of Computer Science and Software Engineering, The University of Newcastle. Erhältlich unter ftp://ftp.cs.newcastle.edu.au/pub/techreports/tr99-05.ps.Z, Abruf: 11.08.2004.

31

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

32

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.

33

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.

34

Gemma Frisius, R.: Libellus de locorum describendorum ratione, [et] de eorum distantijs inveniendis. In: Cosmographicus liber Petri Apiani. Antwerpen, 1533.

35

Gerbessiotis, A. V.; Valiant, L. G.: Direct-Bulk-Synchronous Parallel Algorithms. In: J. of Parallel and Distrib. Computing 22 (1994), Nr. 2, S. 251-267.

36

Goodrich, M. T.: Communication-Efficient Parallel Sorting. In: SIAM J. on Computing 29 (1999), Nr. 2, S. 416-432.

37

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.

38

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.

39

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.

40

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.

41

Hambrusch, S. E.: Models for Parallel Computation. In: Proc. ICPP Workshop on Challenges for Parallel Processing (1996), S. 92-95.

42

Hill, J. M. D.; Donaldson, S. R.; Skillicorn, D. B.: Portability of performance with the BSPlib communications library. In: Proc. Massively Parallel Programming Models (1997), S. 33-42.

43

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

44

Jungnickel, D.: Graphen, Netzwerke und Algorithmen. 3. Aufl. B. I. Wissenschaftsverlag, 1994.

45

Juurlink, B. H. H.; Wijshoff, H. A. G.: Communication primitives for BSP computers. In: Information Processing Letters 58 (1996), S. 303-310.

46

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

47

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.

48

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.

49

Lanthier, M.; Maheshwari, A.; Sack, J.-R.: Approximating Shortest Paths on Weighted Polyhedral Surfaces. In: Algorithmica 30 (2001), Nr. 4, S. 527-562.

50

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

51

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.

52

Mehlhorn, K.; Näher, S.: LEDA. A platform for combinatorial and geometric computing. Cambridge University Press, 1999.

53

Moore, G. E.: Cramming More Components Onto Integrated Circuits. In: Electronica 38 (1965), Nr. 8.

54

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.

55

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

56

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

57

Preparata, F.; Hong, S.: Convex hulls of finite sets of points in two and three dimensions. In: Commun. ACM 20 (1977), S. 87-93.

58

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

59

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

60

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.

61

Shi, H.; Schaeffer, J.: Parallel sorting by regular sampling. In: Journal of Parallel and Distributed Computing 14 (1992), Nr. 4, S. 361-372.

62

Snir, M.; Otto, S.; Huss-Lederman, S.; Walker, D.; Dongarra, J.: MPI: The Complete Reference. Bd. 1, 2. Aufl. MIT Press, 1998.

63

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.

64

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.

65

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

Footnotes

¹

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