×

Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions. (English) Zbl 0875.68842

Summary: For a set of n points in \({\mathbb{R}}^{3}\), we can define the Delaunay triangulation of the point set. For each assignment of weights to the points there is a regular triangulation of the point set. We describe the implementation of algorithms to compute the Delaunay triangulation of an unweighted point set and the regular triangulation of a weighted point set. The algorithms run in expected time O(n log n) for uniformly distributed points and other dense point sets. Worst case point sets, which do not occur very often in practice, require \(O(n^{2})\) expected time. The software described in this paper is available via anonymous ftp at ftp.ncsa.uiuc.edu.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aurenhammer, F., Power diagrams: properties, algorithms, and applications, SIAM J. Comput., 16, 78-96 (1987) · Zbl 0616.52007
[2] Barth, T. J.; Wiltberger, N. L.; Gandhi, A. S., Three-dimensional unstructured grid generation via an incremental insertion and local optimization, (Software Systems for Surface Modeling and Grid Generation. Software Systems for Surface Modeling and Grid Generation, NASA Conference Publication 3143 (1992)), 449-461
[3] Cavendish, J. C.; Field, D. A.; Frey, W. H., An approach to automatic three-dimensional finite element mesh generation, Internat. J. Numer. Meth. Eng., 21, 329-347 (1985) · Zbl 0573.65090
[4] Delaunay, B. N., Sur la sphère vide, Izv. Akad., Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7, 793-800 (1934) · Zbl 0010.41101
[5] Dobkin, D. P.; Laszlo, M. J., Primitives for the manipulation of three-dimensional subdivisions, Algorithmica, 4, 3-32 (1989) · Zbl 0664.68023
[6] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer: Springer Heidelberg · Zbl 0634.52001
[7] Edelsbrunner, H.; Mücke, E. P., Simulation of Simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Trans. Graphics, 9, 66-104 (1990) · Zbl 0732.68099
[8] Edelsbrunner, H.; Shah, N. R., Incremental topological flipping works for regular triangulations, (Proc. 8th Ann. Symp. on Comput. Geom. (1992)), 43-52 · Zbl 0840.68050
[9] George, P. L., Automatic Mesh Generation (1991), Wiley: Wiley Chichester, UK · Zbl 0808.65122
[10] Guibas, L.; Knuth, D.; Sharir, M., Randomized incremental construction of Voronoi and Delaunay diagrams, (Proc. 17th Internat. Colloq. on Automata, Languages and Programming (1990)), 414-431 · Zbl 0765.68207
[11] Joe, B., Three dimensional triangulations from local transformations, SIAM J. Sci. Stat. Comput., 10, 718-741 (1989) · Zbl 0681.65087
[12] Joe, B., Construction of three dimensional triangulations using local transformations, Computer Aided Geometric Design, 8, 123-142 (1991) · Zbl 0729.65120
[13] Lawson, C. L., Software for \(C^1\) surface interpolation, (Rice, J., Mathematical Software III (1977), Academic Press: Academic Press New York), 161-194 · Zbl 0407.68033
[14] Mücke, E. P., Shapes and Implementations in Three-Dimensional Geometry, (Rept. UIUCDCS-R-93-1836 (1993), Comput. Sci. Dept., Univ. Illinois: Comput. Sci. Dept., Univ. Illinois Urbana, IL)
[15] Preparata, F.; Shamos, M., Computational Geometry—An Introduction (1985), Springer: Springer New York · Zbl 0575.68059
[16] Schroeder, W. J.; Shephard, M. S., Geometry-based fully automatic mesh generation and the Delaunay triangulation, Internat. J. Numer. Meth. Eng., 26, 2503-2515 (1988) · Zbl 0662.73052
[17] Voronoi, G. F., Nouvelles applications des paramètres continus à la théorie des formes quadratiques, J. Reine Angew. Math., 133, 97-178 (1907) · JFM 38.0261.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.