Pseudo-Convex Decomposition of Simple Polygons
作者： Alexander Wolff , Stefan Gerdjikov
DOI:
关键词:
摘要: We extend a dynamic-programming algorithm of Keil and Snoeyink for finding minimum convex decomposition simple polygon to the case when both polygons pseudo-triangles are allowed. Our determines pseudo-convex in O(n 3 ) time where n is number vertices polygon. In this way we obtain well-structured with fewer polygons, especially if original has long chains concave vertices.
uni-wuerzburg.de
uni-karlsruhe.de参考文章(6)
Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu, The Zigzag Path of a Pseudo-Triangulation workshop on algorithms and data structures. ,vol. 2748, pp. 377- 388 ,(2003) , 10.1007/978-3-540-45078-8_33
Joachim Gudmundsson, Christos Levcopoulos, Minimum weight pseudo-triangulations foundations of software technology and theoretical computer science. ,vol. 3328, pp. 299- 310 ,(2004) , 10.1007/978-3-540-30538-5_25
Clemens Huemer, Bettina Speckmann, Oswin Aichholzer, Sarah Renkl, Csaba D. Tóth, On Pseudo-Convex Decompositions, Partitions, and Coverings EuroCG. pp. 89- 92 ,(2005)
J. Mark Keil, Decomposing a Polygon into Simpler Components SIAM Journal on Computing. ,vol. 14, pp. 799- 817 ,(1985) , 10.1137/0214056
Thomas Fevens, Henk Meijer, David Rappaport, Minimum convex partition of a constrained point set european workshop on computational geometry. ,vol. 109, pp. 95- 107 ,(2001) , 10.1016/S0166-218X(00)00237-7
MARK KEIL, JACK SNOEYINK, ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS International Journal of Computational Geometry and Applications. ,vol. 12, pp. 181- 192 ,(2002) , 10.1142/S0218195902000803