On Triangulations of a Set of Points in the Plane
A set, V, of points in the plane is triangulated by a subset, T, of the straight line segments whose enpoints 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 segment...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148916 |
| Summary: | A set, V, of points in the plane is triangulated by a subset, T, of the straight line segments whose enpoints 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 several aspects of 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 straight line segments whose endpoints are in V is NP-Complete. |
|---|