Algorithm 860: SimpleS—an extension of Freudenthal's simplex subdivision

ABSTRACT

This article presents a simple efficient algorithm for the subdivision of a d-dimensional simplex in k^d simplices, where k is any positive integer number. The algorithm is an extension of Freudenthal's subdivision method. The proposed algorithm deals with the more general case of k^d subdivision, and is considerably simpler than the RedRefinementND algorithm for implementation of Freudenthal's strategy. The proposed simplex subdivision algorithm is motivated by a problem in the field of robust control theory: the computation of a tight upper bound of a dynamical system performance index by means of a branch-and-bound algorithm.

REFERENCES

• 1: Balakrishnan, V., Boyd, S., and Balemi, S. 1991. Computing the minimum stability degree of parameter-dependent linear systems. In Control of Uncertain Dynamic Systems, S. P. Bhattacharyya and L. H. Keel, Eds. CRC Press, Boca Raton, FL, 359--378.
• 2: C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
• 3: Bey, J. 2000. Simplicial grid refinement: On freudenthal's algorithm and the optimal number of congruence classes. Numer. Math. 85, 1, 1--29.
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: Edelsbrunner, H. and Grayson, D. R. 2000. Edgewise subdivision of a simplex. Discrete Comput. Geom. 24, 707--719.
• 6: Alan Genz , Ronald Cools, An adaptive numerical cubature algorithm for simplices, ACM Transactions on Mathematical Software (TOMS), v.29 n.3, p.297-308, September 2003 [doi>10.1145/838250.838254]
• 7: Gonçalves, E. N., Palhares, R. M., and Takahashi, R. H. C. 2005. Improved optimisation approach to robust H2/H∞ control problem for linear systems. IEE Proceedings Control Theory Applications 152, 2, 171--176.
• 8: Tim N. T. Goodman , Jörg Peters, Be´zier nets, convexity and subdivision on higher-dimensional simplices, Computer Aided Geometric Design, v.12 n.1, p.53-65, Feb. 1995 [doi>10.1016/0167-8396(93)E0057-K]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
Simplex subdivision, mesh generation