On triangulations of a set of points in the plane
- 1 September 1977
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 228-240
- https://doi.org/10.1109/sfcs.1977.21
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.Keywords
This publication has 7 references indexed in Scilit:
- On triangulations of a set of points in the planePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- On the Angle Condition in the Finite Element MethodSIAM Journal on Numerical Analysis, 1976
- Some NP-complete geometric problemsPublished by Association for Computing Machinery (ACM) ,1976
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- Geometric complexityPublished by Association for Computing Machinery (ACM) ,1975
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Triangular Elements in the Finite Element MethodMathematics of Computation, 1970