Francois Labelle
ABSTRACT
We introduce anisotropic Voronoi diagrams, a generalization of multiplicatively weighted Voronoi diagrams suitable for generating guaranteed-quality meshes of domains in which long, skinny triangles are required, and where the desired anisotropy varies over the domain. We discuss properties of anisotropic Voronoi diagrams of arbitrary dimensionality---most notably circumstances in which a site can see its entire Voronoi cell. In two dimensions, the anisotropic Voronoi diagram dualizes to a triangulation under these same circumstances. We use these properties to develop an algorithm for anisotropic triangular mesh generation in which no triangle has an angle smaller than 20A, as measured from the skewed perspective of any point in the triangle.
- Pankaj K. Agarwal, Boris Aronov, and Micha Sharir. Computing Lower Envelopes in Four Dimensions with Applications. Proceedings of the Tenth Annual Symposium on Computational Geometry, pages 348--358. Association for Computing Machinery, 1994. Google Scholar
Digital Library
- Pankaj K. Agarwal, Otfried Schwarzkopf, and Micha Sharir. Overlay of Lower Envelopes and its Applications. Technical Report CS-1994-18, Department of Computer Science, Duke University, 1994. Google ScholarDigital Library
- Thomas Apel. Anisotropic Finite Elements: Local Estimates and Applications. B. G. Teubner Verlag, Stuttgart, 1999.Google Scholar
- Franz Aurenhammer and Herbert Edelsbrunner. An Optimal Algorithm for Constructing the Weighted Voronoi Diagram. Pattern Recognition 17:251--257, 1984.Google ScholarCross Ref
- Frank J. Bossen and Paul~S. Heckbert. A Pliant Method for Anisotropic Mesh Generation. Fifth International Meshing Roundtable, pages 63--74, October 1996.Google Scholar
- Adrian Bowyer. Computing Dirichlet Tessellations. Computer Journal 24(2):162--166, 1981.Google ScholarCross Ref
- Paul-Louis George and Houman Borouchaki. Delaunay Triangulation and Meshing: Application to Finite Elements. Hermes, Paris, 1998.Google Scholar
- Dan Halperin and Micha Sharir. New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visibility in Terrains. Discrete & Computational Geometry 12:313--326, 1994.Google ScholarDigital Library
- Kenneth E. Jansen, Mark S. Shephard, and Mark W. Beall. On Anisotropic Mesh Generation and Quality Control in Complex Flow Problems. Tenth International Meshing Roundtable (Newport Beach, California), pages 341--349. Sandia National Laboratories, October 2001.Google Scholar
- Greg Leibon and David Letscher. Delaunay Triangulations and Voronoi Diagrams for Riemannian Manifolds. Proceedings of the Sixteenth Annual Symposium on Computational Geometry (Hong Kong), pages 341--349. Association for Computing Machinery, June 2000. Google ScholarDigital Library
- Xiang-Yang Li, Shang-Hua Teng, and Alper Angor. Biting Ellipses to Generate Anisotropic Mesh. Eighth International Meshing Roundtable (Lake Tahoe, California), pages 97--108, October 1999.Google Scholar
- Shmuel Rippa. Long and Thin Triangles Can Be Good for Linear Interpolation. SIAM Journal on Numerical Analysis 29(1):257--270, February 1992. Google ScholarDigital Library
- Jim Ruppert. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. Journal of Algorithms 18(3):548--585, May 1995. Google ScholarDigital Library
- Raimund Seidel. Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles. 1978--1988 Ten Years IIG (H. S. Poingratz and W. Schinnerl, editors), pages 178--191. Institute for Information Processing, Graz University of Technology, 1988.Google Scholar
- Micha Sharir. Almost Tight Bounds for Lower Envelopes in Higher Dimensions. Discrete & Computational Geometry 12:327--345, 1994.Google ScholarDigital Library
- Micha Sharir and Pankaj K. Agarwal. Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, New York, 1995. Google ScholarDigital Library
- Jonathan Richard Shewchuk. Tetrahedral Mesh Generation by Delaunay Refinement. Proceedings of the Fourteenth Annual Symposium on Computational Geometry (Minneapolis, Minnesota), pages 86--95. Association for Computing Machinery, June 1998. Google ScholarDigital Library
- ______. What is a Good Linear Finite Element? Interpolation, Conditioning, Anisotropy, and Quality Measures. Manuscript, 2002.Google Scholar
- Kenji Shimada, Atsushi Yamada, and Takayuki Itoh. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles. Sixth International Meshing Roundtable (Park City, Utah), pages 375--390. Sandia National Laboratories, October 1997.Google Scholar
- David F. Watson. Computing the n-dimensional Delaunay Tessellation with Application to Voronoi Polytopes. Computer Journal 24(2):167--172, 1981.Google ScholarCross Ref
Index Terms
- Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation
Recommendations
Guaranteed-quality anisotropic mesh generation for domains with curved boundaries
Anisotropic mesh generation is important for interpolation and numerical modeling. Recently, Labelle and Shewchuk proposed a two-dimensional guaranteed-quality anisotropic mesh generation algorithm called a Voronoi refinement algorithm. This algorithm ...
Anisotropic diagrams: Labelle Shewchuk approach revisited
F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a ...
Locally uniform anisotropic meshing
SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometryVarious definitions of so called anisotropic Voronoi diagrams have been proposed. These diagrams are typically parameterized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a ...
Comments