Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Tóm tắt
Từ khóa
Tài liệu tham khảo
T. Asano, Efficient algorithms for finding the visibility polygon for a polygonal region with holes, Manuscript, University of California at Berkeley.
D. Avis and G. T. Toussaint, An optimal algorithm for determining the visibility of a polygon from an edge,IEEE Trans. Comput.,30 (1981), 910–914.
B. Chazelle, A theorem on polygon cutting with applications,Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982, pp. 339–349.
B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proceedings of the ACM Symposium on Computational Geometry, 1985, pp. 135–146 (also submitted toDiscrete Comput. Geom.).
H. Edelsbrunner, L. Guibas, and J. Stolfi, Optimal point location in monotone subdivisions, Technical Report 2, DEC/SRC, Palo Alto, CA, 1984.
H. A. El Gindy, An efficient algorithm for computing the weak visibility polygon from an edge in simple polygons, Manuscript, McGill University, 1984.
H. A. El Gindy, Hierarchical decomposition of polygons with applications, Ph.D. Dissertation, School of Computer Science, McGill University, 1985.
H. A. El Gindy and D. Avis, A linear algorithm for computing the visibiility polygon from a point,J. Algorithms,2 (1981), 186–197.
A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics,3 (1984), 153–174.
M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Inform. Process. Lett.,7 (1978), 175–179.
R. L. Graham and F. F. Yao, Finding the convex hull of a simple polygon,J. Algorithms,4 (1983), 324–331.
D. H. Greene and D. E. Knuth,Mathematics for the Analysis of Algorithms, Birkhäuser, Boston, 1982.
L. Guibas, E. McCreight, M. Plass, and J. Roberts, A new representation for linear lists,Proceedings of the Ninth ACM Symposium on Theory of Computing, 1977, pp. 49–60.
L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic framework for computational geometry,Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, 1983, pp. 100–111.
S. Huddieston and K. Mehlhorn, A new data structure for representing sorted lists,Acta Inform.,17 (1982), 157–184.
D. T. Lee, Visibility of a simple polygon,Comput. Vision, Graphics Image Process.,22 (1983) 207–221.
D. T. Lee and A. Lin, Computing the visibility polygon from an edge, Manuscript, Northwestern University, 1984.
D. T. Lee and F. P. Preparata, Euclidean shortest paths in the presence of rectilinear battiers,Networks,14 (1984), 393–410.
D. McCallum and D. Avis, A linear algorithm for finding the convex hull of a simple polygon,Inform. Process. Lett.,9 (1979), 201–206.
M. A. Peshkin and A. C. Sanderson, Reachable grasps on a polygon: the convex rope algorithm, Technical Report CMU-RI-TR-85-6, Carnegie-Mellon University, 1985. AlsoIEEE J. Robotics Automat. (1986) (to appear).
F. P. Preparata and K. J. Supowit, Testing a simple polygon for monotonicity,Inform. Process. Lett.,12 (1981), 161–164.
D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach., 32 (1985), 652–686.
S. Suri, Finding minimum link paths inside a simple polygon,Comput. Vision, Graphics Image Process. (1986) (to appear).
R. E. Tarjan,Data Structures and Network Algorithme, CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathemataics, Philadelphia, PA, 1983.
R. E. Tarjan and C. Van Wyk, AnO(n log logn) time algorithm for triangulating simple polygons,SIAM J. Comput. (submitted).
G. Toussaint, Shortest path solves edge-to-edge visibility in a polygon, Technical Report SOCS-85.19, McGill University, 1985.