The Complexity of MaxMin Length Triangulation
classification
💻 cs.CG
cs.DS
keywords
lengthtriangulationalgorithmfindingmaxminproblemapproximateapproximation
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.