Randomly Generating Triangulations of a Simple Polygon
In this paper, we present an O(n2 + |E| 3/2) time algorithm for generating triangulations of a simple polygon at random with uniform distribution, where n and |E| are the number of vertices and diagonal edges in the given polygon, respectively. The current best algorithm takes O(n4) time. We also derive algorithms for computing the expected degree of each vertex, the expected number of ears, the expected number of interior triangles, and the expected height of the corresponding tree in such a triangulated polygon. These results are not known for simple polygon. All these algorithms are dominated by the O(n2 + |E|3/2)time triangulation counting algorithm. If the results of the triangulation counting algorithm are given, then the triangulation generating algorithm takes O(n log n) time only. All these algorithms are simple and easy to be implemented.
Q. Ding J. Qian W. Tsang C. Wang
Zhejiang Radio & TV Transmission Center, HangZhou, China Department of Computer Science, Memorial University of Newfoundland St. Johns, Newfoundland, Canada Department of Computer Science, The University of Hong Kong Hong Kong, China
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
471-480
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）