1977/09/01 by Errol L. Lloyd · 3 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Triangulation #Minimum-weight triangulation #Combinatorics #Point set triangulation #Counterexample #Euclidean geometry #Mathematics #Plane (geometry) #Pitteway triangulation #Line segment #Line (geometry) #Set (abstract data type) #Delaunay triangulation #Point (geometry) #Discrete mathematics #Constrained Delaunay triangulation #Computer science #Geometry
paper · doi:10.1109/sfcs.1977.21
openalex publication_date 1977/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A set, V, of points in the plane is triangulated by a subset T, of the straight-line segments whose endpoints are in V, if T is a maximal subset such that the line segments in T intersect only at their endpoints. The weight of any triangulation is the sum of the Euclidean lengths of the line segments in the triangulation. We examine two problems involving triangulations. We discuss the problem of finding a minimum weight triangulation among all triangulations of a set of points and give counterexamples to two published solutions to this problem. Secondly, we show that the problem of determining the existence of a triangulation, in a given subset of the line segments whose endpoints are in V, is NP-Complete.