摘要: For the convex polygon P having n vertices entirely contained in a K m vertices, an optimal algorithm with running time O(n + m) is presented to compute and name regions boundary of from which it possible illuminate exterior P. It also shown that this illumination region can be used improve worst case O(nm) related two dimensional simplex coverability so too has m), thus within constant factor.
computer.org
sci-hub.se 参考文章(9)
Azaria Paz, Introduction to probabilistic automata (Computer science and applied mathematics) Academic Press, Inc.. ,(1971)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
D. T. Lee, F. P. Preparata, An Optimal Algorithm for Finding the Kernel of a Polygon Journal of the ACM. ,vol. 26, pp. 415- 421 ,(1979) , 10.1145/322139.322142
Michael Ian Shamos, Dan Hoey, Closest-point problems foundations of computer science. pp. 151- 162 ,(1975) , 10.1109/SFCS.1975.8
R.L. Graham, An efficient algorith for determining the convex hull of a finite planar set Information Processing Letters. ,vol. 1, pp. 132- 133 ,(1972) , 10.1016/0020-0190(72)90045-2
D.T. Lee, F.P. Preparata, The all nearest-neighbor problem for convex polygons Information Processing Letters. ,vol. 7, pp. 189- 192 ,(1978) , 10.1016/0020-0190(78)90066-2
F. P. Preparata, S. J. Hong, Convex hulls of finite sets of points in two and three dimensions Communications of the ACM. ,vol. 20, pp. 87- 93 ,(1977) , 10.1145/359423.359430
Silio, An Efficient Simplex Coverability Algorithm in E2 with Application to Stochastic Sequential Machines IEEE Transactions on Computers. ,vol. 28, pp. 109- 120 ,(1979) , 10.1109/TC.1979.1675300
Gene H. Ott, Reconsider the state minimization problem for stochastic finite state systems foundations of computer science. pp. 267- 273 ,(1966) , 10.1109/SWAT.1966.20