An efficient algorithm for decomposing a polygon into star-shaped polygons
作者： D. Avis , G.T. Toussaint
DOI: 10.1016/0031-3203(81)90002-9
关键词:
摘要: Abstract In this paper we show how a theorem in plane geometry can be converted into O(n log n) algorithm for decomposing polygon star-shaped subsets. The computational efficiency of new decomposition contrasts with the heavy burden existing methods.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(13)
Kiyoshi Maruyama, Study of visual shape perception ,(1972) , 10.2172/4623800
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Bernard Chazelle, David Dobkin, Decomposing a polygon into its convex parts symposium on the theory of computing. pp. 38- 48 ,(1979) , 10.1145/800135.804396
Michael R. Garey, David S. Johnson, Franco P. Preparata, Robert E. Tarjan, Triangulating a simple polygon Information Processing Letters. ,vol. 7, pp. 175- 179 ,(1978) , 10.1016/0020-0190(78)90062-5
Theodosios Pavlidis, Representation of figures by labeled graphs Pattern Recognition. ,vol. 4, pp. 5- 17 ,(1972) , 10.1016/0031-3203(72)90016-7
D. T. Lee, F. P. Preparata, Location of a Point in a Planar Subdivision and Its Applications SIAM Journal on Computing. ,vol. 6, pp. 594- 606 ,(1977) , 10.1137/0206043
Theodosios Pavlidis, A review of algorithms for shape analysis Computer Graphics and Image Processing. ,vol. 7, pp. 243- 258 ,(1978) , 10.1016/0146-664X(78)90115-6
Steve Fisk, A short proof of Chvátal's Watchman Theorem Journal of Combinatorial Theory, Series B. ,vol. 24, pp. 374- ,(1978) , 10.1016/0095-8956(78)90059-X
Schachter, Decomposition of Polygons into Convex Sets IEEE Transactions on Computers. ,vol. 27, pp. 1078- 1082 ,(1978) , 10.1109/TC.1978.1675001
V Chvátal, A combinatorial theorem in plane geometry Journal of Combinatorial Theory, Series B. ,vol. 18, pp. 39- 41 ,(1975) , 10.1016/0095-8956(75)90061-1