Mesh refinement via bidirected flows: modeling, complexity, and computational results

ABSTRACT

We investigate a problem arising in the computer-aided design of cars, planes, ships, trains, and other motor vehicles and machines: refine a mesh of curved polygons, which approximates the surface of a workpiece, into quadrilaterals so that the resulting mesh is suitable for a numerical analysis. This mesh refinement problem turns out to be strongly NP-hard In commercial CAD systems, this problem is usually solved using a gree dy approach. However, these algorithms leave the user a lot of patchwork to do afterwards. We introduce a new global approach, which is based on network flow techniques. Abstracting from all geometric and numerical aspects, we obtain an undirected graph with upper and lower capacities on the edges and some additional node constraints. We reduce this problem to a sequence of bidirected flwo problems (or, equivalently, to b-matching problems). For the first time, network flow techniques are applied to a mesh refinement problem. This approach avoids the local traps of greedy approaches and yields solutions that require significantly less additional patchwork.

REFERENCES

• 1: AHUJA, R. K., MAGNANTI, T. L., AND ORLIN, J.B. 1993. Network Flows. Prentice-Hall, Englewood Cliffs, N.J.
• 2: Richard P. Anstee, A polynomial algorithm for b-matchings: an alternative approach, Information Processing Letters, v.24 n.3, p.153-157, February 1987 [doi>10.1016/0020-0190(87)90178-5]
• 3: BABUSKA, I., AND AzIz, A. 1976. On the angle condition in the finite element method. SIAM J. Num. Anal. 13, 214-227.
• 4: BERN, M., AND EPPSTEIN, D. 1992. Mesh generation and optimal triangulation. In Computing in ~Euclidean Geometry, D.-Z. Du and F. K. Hwang, eds. World Scientific, Singapore, pp. 23-90.
• 5: DERIGS, U. 1988. Programming in networks and graphs. In Lecture Notes in Economics and Mathematical Systems, vol. 300. Springer-Verlag, Berlin, Germany.
• 6: EDMONDS, J. 1967. An Introduction to Matching. Lecture Notes. Univ. Michigan, Ann Arbor, Ann Arbor, Mich.
• 7: K. Ho-Le, Finite element mesh generation methods: a review and classification, Computer-Aided Design, v.20 n.1, p.27-38, Feb., 1988 [doi>10.1016/0010-4485(88)90138-8]
• 8: JOE, 13. 1995. Quadrilateral mesh generation in polygonal regions. Comput. Aided Des. 27, 209 -222.
• 9: KRAUSE, G. 1991. Interactive finite element preprocessing with ISAGEN. Fin. Element News 15.
• 10: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
• 11: MILLER, D. t., AND PEKNY, J.F. 1995. A staged primal-dual algorithm for perfect b-matching with edge capacities. ORSA J. Comput. 7, 298-320.
• 12: M(3HRING, R. H., AND MULLER-HANNEMANN, M. 1995. Cardinality matching: Heuristic search for augmenting paths. Tech. Rep. no. 439/1995. Technische Universitfit Berlin, Berlin, Germany. (Available via anonymous ftp from ftp.math.tu-berlin.de; cd pub/Preprints/combi; file Report-439-1995 .ps. Z.)
• 13: MULLER-HANNEMANN, M., AND SCHWARTZ, A. 1997. Mesh refinement in quadrilaterals without template restrictions. Manuscript.
• 14: MOLLER-HANNEMANN, M., AND WEIHE, K. 1996. Minimum strictly convex quadrangulations of convex polygons. Preprint No. 13. Dept. Math. Comput. Sci., Univ. Konstanz, Konstanz, Germany. (Available via anonymous ftp from ftp.informatik.uni-konstanz.de; cd pub/preprints/1996, file preprint-013 .ps. Z.)
• 15: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 16: PULLEYBLANK, W. 1973. Faces of matching polyhedra. Ph.D. dissertation. Faculty of Mathematics, Univ. Waterloo, Waterloo, England.
• 17: RIPPENHAUSEN-LIPA, H., WAGNER, D., AND WEIHE, K. 1995. Efficient algorithms for disjoint paths in planar graphs. In DIMACS Series in Discrete Mathematics and Computer Science, vol. 20 (from the special year on combinatorial optimization). American Mathematical Society, Providence, R. I., pp. 295-354.
• 18: SRINIVASAN, V., NACKMAN, L. R., TANG, J.-M., AND MEHKAT, S. N. 1992. Automatic mesh generation using the symmetric axis transformation of polygonal domains. In Proc. IEEE 80, 1485-1501.
• 19: STRANG, G., AND FIX, a. J. 1973. An Analysis of the Finite Element Method. Prentice-Hall, Englewood Cliffs, N.J.
• 20: TAM, T. K. H., AND ARMSTRONG, C. G. 1993. Finite element mesh control by integer programming. Int. J. Num. Meth. Eng. 36, 2581-2605.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation

Keywords:
NP-completeness, b-matching problem, augmenting paths, bidirected flows, mesh generation, templates