An Algorithm for Generating a 5-Optimal Triangulation

Yinfeng Xu and Wenqiang Dai
School of Management, Xi'an Jiaotong University,
Xi'an, 710049
P.R.China

Abstract    
A triangulation T(S) is called a k-optimal triangulation for 4 k < n if every k-sided simply polygon drawn from T(S) is optimally triangulated by some edges of T(S) with the minimum weight sum criteria. Though some 4-optimal triangulations have already been obtained efficiently, there is no any result on how to get a 5-optimal triangulation. In this paper, we show a property on the 5-optimal triangulation and present an algorithm to generate a 5-optimal triangulation for any given points set and for some special case, our algorithm can also produce a 6-optimal triangulation.