Files in this item



application/pdf9996652.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Sliver -Free Three Dimensional Delaunay Mesh Generation
Author(s):Li, Xiangyang
Doctoral Committee Chair(s):Shang-Hua Teng
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:The second algorithm adds points to generate well-shaped meshes. It is based on the following observations. Any tetrahedron will disappear from the Delaunay triangulation if a point is added inside the circumsphere of the tetrahedron. Among the tetrahedra created by inserting this new point there could be tetrahedra with large radius-edge ratios, or slivers, or both. However, the new point is incident to every new tetrahedron. We first eliminate tetrahedra with large radius-edge ratios. We then select the point that avoids creating any small slivers when inserting point inside the circumsphere of slivers. We show that the algorithm will not introduce short edges to the Delaunay triangulation. A simple volume argument implies that the algorithm terminates and generates a well-shaped Delaunay mesh. The generated mesh has a good grading. The number of mesh elements is within a small constant factor of any almost-good mesh for that given domain. We also describe some variations of this refinement-based algorithm. In particular, we show that inserting points near sinks instead of circumcenters of bad tetrahedra also generates sliver-free Delaunay meshes.
Issue Date:2001
Description:108 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2001.
Other Identifier(s):(MiAaPQ)AAI9996652
Date Available in IDEALS:2015-09-25
Date Deposited:2001

This item appears in the following Collection(s)

Item Statistics