Algorithm 772: STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere

ABSTRACT

STRIPACK is a Fortran 77 software package that employs an incremental algorithm to construct a Delaunay triangulation and, optionally, a Voronoi diagram of a set of points (nodes) on the surface of the unit sphere. The triangulation covers the convex hull of the nodes, which need not be the entire surface, while the Voronoi diagram covers the entire surface. The package provides a wide range of capabilities including an efficient means of updating the triangulation with nodal additions or deletions. For N nodes, the storage requirement for the triangulation is 13N integer storage locations in addition to 3N nodal corrdinates. Using an off-line algorithm and work space of size 3N, the triangulation can be constructed with time complexity O(NlogN).

REFERENCES

• 1: AUGENBAUM, J. M. AND PESKIN, C.S. 1985. On the construction of the Voronoi mesh on a sphere. J. Comput. Phys. 59, 177-192.
• 2: C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
• 3: CLINE, A. K. AND RENKA, R. J. 1984. A storage-efficient method for construction of a Thiessen triangulation. Rocky Mt. J. Math. 14, 1, 119-139.
• 4: A. K. Cline , R. J. Renka, A constrained two-dimensional triangulation and the solution of closest node problems in the presence of barriers, SIAM Journal on Numerical Analysis, v.27 n.5, p.1305-1321, Oct. 1990 [doi>10.1137/0727074]
• 5: DELAUNAY, B. 1934. Sur la sphere vide. Bull. Acad. Sci. USSR 7, 793-800.
• 6: FOHLMEISTER, J. F. AND RENKA, R.J. 1994. Hotspots, mantle convection and plate tectonics: A synthetic calculation. Pure Appl. Geophys. 143, 673-695.
• 7: FOHLMEISTER, J. F., RENKA, R. J., AND STOUT, J. H. 1990. Lithospheric plate motions predicted by a quantitative theory. Trans. Am. Geophys. Union 71, 43 (Oct.).
• 8: GUIBAS, L. J., KNUTH, D. E., AND SHARIR, M. 1992. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 381-413.
• 9: LAWSON, C.L. 1977. Software for C1 surface interpolation. In Mathematical Software III, J. R. Rice, Ed. Academic Press, Inc., Orlando, FL, 161-194.
• 10: LAWSON, C.L. 1984. C1 surface interpolation for scattered data on a sphere. Rocky Mt. J. Math. 14, 1, 177-202.
• 11: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 12: Robert J. Renka, Interpolation of data on the surface of a sphere, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.417-436, Dec. 1984 [doi>10.1145/2701.2703]
• 13: Robert J. Renka, Algorithm 623: Interpolation on the Surface of a Sphere, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.437-439, Dec. 1984 [doi>10.1145/2701.356107]
• 14: R. J. Renka, Algorithm 751: TRIPACK: a constrained two-dimensional Delaunay triangulation package, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.1-8, March 1996 [doi>10.1145/225545.225546]
• 15: Robert J. Renka, Algorithm 773: SSRFPACK: interpolation of scattered data on the surface of a sphere with a surface under tension, ACM Transactions on Mathematical Software (TOMS), v.23 n.3, p.435-442, Sept. 1997 [doi>10.1145/275323.275330]
• 16: RHYNSBURGER, D. 1973. Analytic delineation of Thiessen polygons. Geograph. Anal. 5, 133-144.
• 17: SIBSON, R. 1978. Locally equiangular triangulations. Comput. J. 21,243-245.
• 18: VORONOI, G. 1908. Nouvelles applications des parametres continuis ~ la theorie des formes quadratiques: Deuxi~me m~morie: Recherches sur les parall~lo~dres primitifs. J. Reine Angew Math. 134, 198-287.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms

Keywords:
Delaunay triangulation, Dirichlet tessellation, Thiessen regions, Voronoi diagram, sphere