Optimal Dissection of Simplices

The bisection algorithm is a minimax procedure for locating a fixed point of a continuous function taking an interval into itself. The algorithm can also be viewed as dissecting a 1-simplex (interval) into smaller 1-simplices by the insertion of a point. We generalize the latter problem to n dimensions and ask for a sequential dissection scheme to minimize the maximum diameter of a subsimplex after k dissections. We obtain bounds on the asymptotic rate at which the minimax diameter can be reduced and dissection schemes that approach these bounds. Based on these schemes we give near-optimal triangulations for computing fixed points.