A New Triangulation for Simplicial Algorithms

Tjriangulations are used in simplicial algorithms to find the fixed points of continuous functions or upper semicontinuous mappings; applications arise from economics and optimization. The performance of simplicial algorithms is very sensitive to the triangulation used. Using a facetal description, Dang’s $D_1 $ triangulation is modified to obtain a more efficient triangulation of the unit hypercube in $R^n $, and then, by means of translations and reflections, we derive a new triangulation, $D'_1 $, of $R^n $. It is shown that $D'_1 $ uses fewer simplices (asymptotically 30 percent fewer) than $D_1 $ while achieving comparable scores for other performance measures such as the diameter and the surface density. The results of Haiman’s recursive method for getting asymptotically better triangulations from $D_1 $, $D'_1 $ and other triangulations are also compared.