Improved heuristics for the minimum weight triangulation problem |
| |
Authors: | Yinfeng Xu Dian Zhou |
| |
Institution: | (1) School of Management, Xi'an Jiaotong University, 710049 Xi'an, China;(2) Department of Electrical Engineering, the University of North Carolina at Charlotte, USA |
| |
Abstract: | Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n
3) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|