On triangulations of a set of points in the plane

Abstract

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.