Name
Abstract | ||
|---|---|---|
We show how to triangulate a three dimensional polyhedral region with holes. Our triangulation is optimal in the following two senses. First, our triangulation achieves the best possible aspect ratio up to a constant. Second, for any other triangulation of the same region into m triangles with bounded aspect ratio, our triangulation has size n = O(m). Such a triangulation is desired as an initial mesh for a finite element mesh refinement algorithm. Previous three dimensional triangulation schemes either worked only on a restricted class of input, or did not guarantee well-shaped tetrahedra, or were not able to bound the output size. We build on some of the ideas presented in previous work by Bern, Eppstein, and Gilbert, who have shown how to triangulate a two dimensional polyhedral region with holes, with similar quality and optimality bounds. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1145/142675.142720 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
initial mesh,possible aspect ratio,quality mesh generation,m triangle,dimensional polyhedral region,finite element mesh refinement,dimensional triangulation scheme,bounded aspect ratio,size n,previous work,output size,three dimensions,aspect ratio,mesh generation,linear programming,technical report,three dimensional,combinatorial optimization,computer science,computational geometry | Triangulation (geometry),Discrete mathematics,Combinatorics,Minimum-weight triangulation,Triangulation (social science),Triangulation,Constrained Delaunay triangulation,Mesh generation,Mathematics,Delaunay triangulation,Pitteway triangulation | Conference |
ISBN | Citations | PageRank |
0-89791-517-8 | 60 | 22.61 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Scott A. Mitchell | 1 | 461 | 77.77 |
| Stephen A. Vavasis | 2 | 607 | 135.74 |