2012/08/01 by Sándor P. Fekete, Fekete, Sándor P.
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1208.0202
7 pages, 3 figures
arxiv created 2012/08/01 · openalex publication_date 2012/08/01 · arxiv updated 2012/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1991, Edelsbrunner and Tan gave an O(n2) 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.