STRIPACK - DELAUNAY TRIANGULATION AND VORONOI DIAGRAM ON THE SURFACE OF A SPHERE

Authors
Citation
Rj. Renka, STRIPACK - DELAUNAY TRIANGULATION AND VORONOI DIAGRAM ON THE SURFACE OF A SPHERE, ACM transactions on mathematical software, 23(3), 1997, pp. 416-434
Citations number
17
Language
INGLESE
art.tipo
Article
ISSN journal
0098-3500
Volume
23
Issue
3
Year of publication
1997
Pages
416 - 434
Database
ISI
SICI code
0098-3500(1997)23:3<416:S-DTAV>2.0.ZU;2-3
Abstract
STRIPACK is a Fortran 77 software package that employs an incremental algorithm to construct a Delaunay triangulation and, optionally, a Vor onoi diagram of a set of points (nodes) on the surface of the unit sph ere. The triangulation covers the convex hull of the nodes, which need not be the entire surface, while the Voronoi diagram covers the entir e 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 triangulat ion is 13N integer storage locations in addition to 3N nodal coordinat es. Using an off-line algorithm and work space of size 3N, the triangu lation can be constructed with time complexity O(NlogN).