Erased arrangements of lines and convex decompositions of polyhedra
作者： J.E. Hershberger , J.S. Snoeyink
DOI: 10.1016/S0925-7721(97)00024-2
关键词:
摘要: Abstract In 1984, B. Chazelle proposed a notch-cutting procedure for decomposing non-convex polyhedron into convex pieces. This paper shows that notch-cutting, when applied to with n faces and r reflex dihedral angles, gives decomposition Θ(nr + 7 3 ) worst-case complexity. The upper lower bounds are obtained by studying the complexity of horizon segment in an incrementally-constructed erased arrangement lines. Efficient deterministic algorithms compute this also described.
elsevier.com
sci-hub.se 参考文章(26)
Discrete and Computational Geometry: Papers from the DIMACS Special Year Association for Computing Machinery. ,vol. 6, ,(1991) , 10.1090/DIMACS/006
Michael S. Paterson, F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling Discrete & Computational Geometry. ,vol. 5, pp. 485- 503 ,(1990) , 10.1007/BF02187806
Rephael Wenger, Upper bounds on geometric permutations for convex sets Discrete & Computational Geometry. ,vol. 5, pp. 27- 33 ,(1990) , 10.1007/BF02187777
B. Chazelle, L. Palios, Triangulating a non-convex polytype symposium on computational geometry. ,vol. 5, pp. 393- 400 ,(1989) , 10.1145/73833.73876
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres Discrete & Computational Geometry. ,vol. 5, pp. 99- 160 ,(1990) , 10.1007/BF02187783
Sergiu Hart, Micha Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes Combinatorica. ,vol. 6, pp. 151- 177 ,(1986) , 10.1007/BF02579170
Barry Joe, Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions International Journal for Numerical Methods in Engineering. ,vol. 37, pp. 693- 713 ,(1994) , 10.1002/NME.1620370409
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
David Dobkin, Leonidas Guibas, John Hershberger, Jack Snoeyink, An efficient algorithm for finding the CSG representation of a simple polygon Algorithmica. ,vol. 10, pp. 1- 23 ,(1993) , 10.1007/BF01908629
Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm SIAM Journal on Computing. ,vol. 13, pp. 488- 507 ,(1984) , 10.1137/0213031