Edge insertion for optimal triangulations (Q2368129)

This paper presents an abstract formulation of a minimax-angle algorithm, called the edge-insertion paradigm, as a general method to compute optimal triangulations. Optimal triangulations figure in areas such as finite element analysis, computational geometry and surface approximations. The paradigm is an abstraction of the algorithm introduced by \textit{H. Edelsbrunner}, \textit{T. S. Tan}, \textit{R. Waupotitsch} [SIAM J. Sci. Stat. Comput. 13, No. 4, 994-10008 (1992; Zbl 0754.65093)]. Two classes of criteria are formulated for which the paradigm computes a global optimum. Application of the paradigm to obtain polynomial time algorithm is discussed. The algorithm is available through anonymous \(ftp\) from the directory ``/SGI/ MinMaxer'' at the site ``ftp.nsca.UIUC.edu.''.