Normal art galleries: Wall in – all in

Computational Geometry - Tập 46 - Trang 7-16 - 2013
Zoran Šunić1
1Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA

Tài liệu tham khảo

I. Balaban, An optimal algorithm for finding segment intersections, in: Proc. 11th Annu. ACM Sympos. Comput. Geom., 1995, pp. 211–219. Bentley, 1979, Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., 28, 643, 10.1109/TC.1979.1675432 de Berg, 2000, Computational Geometry, 10.1007/978-3-662-04245-8 Bjorling-Sachs, 1998, Edge guards in rectilinear polygons, Comput. Geom., 11, 111, 10.1016/S0925-7721(98)00024-8 Bjorling-Sachs, 1995, An efficient algorithm for guard placement in polygons with holes, Discrete Comput. Geom., 13, 77, 10.1007/BF02574029 Bose, 2002, Efficient visibility queries in simple polygons, Comput. Geom., 23, 313, 10.1016/S0925-7721(01)00070-0 Chazelle, 1992, An optimal algorithm for intersecting line segments in the plane, J. ACM, 39, 1, 10.1145/147508.147511 Chvátal, 1975, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B, 18, 39, 10.1016/0095-8956(75)90061-1 El-Gindy, 1981, A linear algorithm for computing the visibility polygon from a point, J. Algorithms, 2, 186, 10.1016/0196-6774(81)90019-5 F. Hoffmann, M. Kaufman, K. Kriegel, The art gallery problem for polygons with holes, in: Proc. of the 32nd Symposium on Foundations of Computer Science, 1991, pp. 39–48. Joe, 1986, Corrections to Leeʼs visibility polygon algorithm, BIT, 27, 458, 10.1007/BF01937271 Kahn, 1983, Traditional galleries require fewer watchmen, SIAM J. Algebr. Discrete Methods, 4, 194, 10.1137/0604020 Klee, 1977, Can the measure of ⋃1n[ai,bi] be computed in less than O(nlogn) steps?, Amer. Math. Monthly, 84, 284, 10.2307/2318871 Lee, 1983, Visibility of a simple polygon, Comput. Vis. Graph. Image Process., 22, 207, 10.1016/0734-189X(83)90065-8 OʼRourke, 1983, An alternate proof of the rectilinear art gallery theorem, J. Geom., 21, 118, 10.1007/BF01918136 OʼRourke, 1983, Galleries need fewer mobile guards: a variation on Chvátalʼs theorem, Geom. Dedicata, 14, 273 OʼRourke, 1987, Art Gallery Theorems and Algorithms Preparata, 1985, Computational Geometry, 10.1007/978-1-4612-1098-6 J.R. Sack, G.T. Toussaint, Guard placement in rectilinear polygons, in: Computational Morphology, 1988, pp. 153–176. Urrutia, 2000, Art gallery and illumination problems, 973