Triangulating a Convez Polygon with Small Number of Non-standard Bars Eztended Abstract
For a given convex polygon with inner angle no less than 2/3π and boundary edge bounded by l, αl for 1≤α≤1.4, where l is a given standard bars length, we investigate the problem of triangulating the polygon using some Steiner points such that (i) the length of each edge in triangulation is bounded by βl, 2l, where β is a given constant and meets 0<β<1/2, and (ii) the number of non-standard bars in the triangulation is minimum. This problem is motivated by practical applications and has not been studied previously. In this paper, we present a heuristic to solve the above problem, which is based on the heuristic to generate a triangular mesh with more number of standard bars and shorter maximal edge length, and a process to make the length of each edge lower bounded. Our procedure is simple and easily implemented for this problem, and we prove that it has good performance guaranteed.
Yinfeng Xu Wenqiang Dai Naoki Katoh Makoto Ohsaki
School of Management, Xian Jiaotong University, Xian,710049, P.R. China The State Key Lab for Manu School of Management, Xian Jiaotong University, Xian, 710049, P.R. China Department of Architecture and Architectural Engineering, Kyoto University Kyotodaigaku-Katsura, Nis
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
481-489
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）