Journal article
NEW RESULTS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
Algorithmica, Vol.12(6), pp.533-552
12/01/1994
DOI: 10.1007/BF01188718
Abstract
Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is known to find a triangulation of minimum weight, nor is the minimum weight triangulation problem known to be NP-hard. This paper proposes a new heuristic algorithm that triangulates a set of n points in O(n(3)) time and that never produces a triangulation whose weight is greater than that of a greedy triangulation. The algorithm produces an optimal triangulation if the points are the vertices of a convex polygon. Experimental results indicate that this algorithm rarely produces a nonoptimal triangulation and performs much better than a seemingly similar heuristic of Lingas. In the direction of showing the minimum weight triangulation problem is NP-hard, two generalizations that are quite close to the minimum weight triangulation problem are shown to be NP-hard.
Details
- Title: Subtitle
- NEW RESULTS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
- Creators
- L S Heath - Virginia TechS V Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Algorithmica, Vol.12(6), pp.533-552
- DOI
- 10.1007/BF01188718
- ISSN
- 0178-4617
- eISSN
- 1432-0541
- Publisher
- Springer Nature
- Number of pages
- 20
- Language
- English
- Date published
- 12/01/1994
- Academic Unit
- Computer Science
- Record Identifier
- 9984259413302771
Metrics
5 Record Views