Title:	Delaunay triangulation in 3D: technical report no. DCSE/TR-2002-02
Authors:	Maur, Pavel
Issue Date:	2002
Publisher:	University of West Bohemia in Pilsen
Document type:	zpráva report
URI:	http://www.kiv.zcu.cz/publications/ http://hdl.handle.net/11025/21617
Keywords:	Delaunayho triangulace;3D;čtyřstěn;plovoucí desetinná čárka
Keywords in different language:	Delaunay triangulation;3D;tetrahedron;floating point
Abstract in different language:	The Delaunay triangulation is one of the most popular and most often used methods in problems related to the generation of meshes. A lot of the optimal properties of Delaunay triangulation are known in 2D, where it has been intensively studied during the last twenty years, although the fundamentals were formulated early in the twentieth century (Voronoi, 1908 and Delaunay, 1934). This thesis presents Delaunay triangulation without addition or displacement of points in 3D space. It focuses on its properties and on a summarization of existing sequential algorithms. Also our experience with the implementation of the incremental insertion algorithm is presented and observed features are discussed. The properties of Delaunay triangulation in 3D (or generally in higher dimensions) are not as good as in 2D and different kinds of methods are used mainly to remove the tetrahedra of undesirable shape. Although this area of research was not within our main scope, we present an existing simple method for tetrahedra shape improvement. We have implemented this method and our results are presented and discussed. In the implementation of algorithms, which have to deal with inprecise floating-point arithemtic on real computers, the question of numerical stability becomes very important for the proper function of the implementation. We introduce several existing approaches for increasing the numerical stability of algorithms, two of them for an exact evaluation of geometric predicates are presented in more details. We made a comparison of them and we mention the results of incorporating one of them in our implementation.
Rights:	© University of West Bohemia in Pilsen
Appears in Collections:	Zprávy / Reports (KIV)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.