Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation

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 20^A, as measured from the skewed perspective of any point in the triangle.

REFERENCES

• 1: Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Computing envelopes in four dimensions with applications, Proceedings of the tenth annual symposium on Computational geometry, p.348-358, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178081]
• 2: K P Agarwal , Otfried Schwarzkopf , Micha Sharir, The Overlay of Lower Envelopes and its Applications, Duke University, Durham, NC, 1994
• 3: Thomas Apel. Anisotropic Finite Elements: Local Estimates and Applications. B. G. Teubner Verlag, Stuttgart, 1999.
• 4: Franz Aurenhammer and Herbert Edelsbrunner. An Optimal Algorithm for Constructing the Weighted Voronoi Diagram. Pattern Recognition 17:251--257, 1984.
• 5: Frank J. Bossen and Paul~S. Heckbert. A Pliant Method for Anisotropic Mesh Generation. Fifth International Meshing Roundtable, pages 63--74, October 1996.
• 6: Adrian Bowyer. Computing Dirichlet Tessellations. Computer Journal 24(2):162--166, 1981.
• 7: Paul-Louis George and Houman Borouchaki. Delaunay Triangulation and Meshing: Application to Finite Elements. Hermes, Paris, 1998.
• 8: 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.
• 9: 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.
• 10: Greg Leibon , David Letscher, Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, Proceedings of the sixteenth annual symposium on Computational geometry, p.341-349, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336221]
• 11: 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.
• 12: Shmuel Rippa, Long and thin triangles can be good for linear interpolation, SIAM Journal on Numerical Analysis, v.29 n.1, p.257-270, Feb. 1992 [doi>10.1137/0729017]
• 13: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 14: 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.
• 15: Micha Sharir. Almost Tight Bounds for Lower Envelopes in Higher Dimensions. Discrete & Computational Geometry 12:327--345, 1994.
• 16: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 17: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 18: ______. What is a Good Linear Finite Element? Interpolation, Conditioning, Anisotropy, and Quality Measures. Manuscript, 2002.
• 19: 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.
• 20: David F. Watson. Computing the n-dimensional Delaunay Tessellation with Application to Voronoi Polytopes. Computer Journal 24(2):167--172, 1981.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
anisotropic Voronoi diagram, anisotropic mesh generation