  In 1991, Edelsbrunner and Tan gave an O(n^2) algorithm for finding the MinMax
Length triangulation of a set of points in the plane. In this paper we resolve
one of the open problems stated in that paper, by showing that finding a MaxMin
Length triangulation is an NP-complete problem. The proof implies that (unless
P=NP), there is no polynomial-time approximation algorithm that can approximate
the problem within any polynomial factor.
