Quadrilateral meshes with bounded minimum angle

ABSTRACT

We present an algorithm that constructs a strictly convex quadrilateral mesh for a simple polygonal region in which no newly created angle is smaller than D(18.43) (=arctan(1/3)). This is the first known result on quadrilateral mesh generation with a provable guarantee on the minimum angle.

REFERENCES

• 1: D. J. Allman. A quadrilateral finite element including vertex rotations for plane elasticity analysis. Int. J. for Numerical Methods in Engineering, 26:717--730, 1988.
• 2: F. B. Atalay, S. Ramaswami, and D. Xu. Quadrilateral meshes with bounded minimum angle. In Proc. 17th International Meshing Roundtable, pages 73--91. Springer-Verlag, 2008.
• 3: S. Benzley, E. Perry, K. Merkley, B. Clark, and G. Sjaardema. A Comparison of All Hexahedral and All Tetrahedral Finite Element Meshes for Elastic and Elastic--Plastic Analysis. In Proceedings of the 4th International Meshing Roundtable, pages 179--192, 1995.
• 4: M. Bern and D. Eppstein. Quadrilateral meshing by circle packing. In Proc. 6th International Meshing Roundtable, pages 7--19, 1997.
• 5: Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
• 6: T. Blacker and M. Stephenson. Paving: A new approach to automated quadrilateral mesh generation. Int. J. for Numerical Methods in Engineering, 32(4):811--847, 1991.
• 7: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 8: B. P. Johnston, J. M. Sullivan, and A. Kwasnik. Automatic conversion of triangular finite meshes to quadrilateral elements. Int. J. of Numerical Methods in Engineering, 31(1):67--84, 1991.
• 9: Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
• 10: J. Shewchuk. Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery. In Proceedings of the 11th International Meshing Roundtable, pages 193--204, 2002.
• 11: O. C. Zienkiewicz and R. L. Taylor. The finite element method. McGraw-Hill, 1989.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
quadrilateral mesh generation