Feature Column from the AMS

Diagonals: Part II

5. References

Aggarwal, A., The art gallery theorem: its variations, applications and algorithmic aspects, Ph.D. Thesis, Johns Hopkins University, Baltimore, 1984.

Aggarwal, A., and S. Suri, Computing the longest diagonal of a simple polygon, Inform. Process. Lett., 35 (1990) 13-18.

Bjorling-Sachs, I., Tight bound for edge guards in rectilinear monotone polygons, DIMACS Tech. Report, 93-12, Rutgers University, 1993.

Chazelle, B., Computational geometry and convexity, Ph. D. Thesis, Yale University, New Haven, 1980.

Chazelle, B., Triangulating a simple polygon in linear time, Disc. Comput. Geom., 6 (1991) 485-524.

Chazelle, B. and D. Dobkin, Optimal convex decompositions, In Computational Geometry, (G. Toussaint, ed.), Elsevier, North Holland, Amsterdam, 1985, p. 63-133.

Chin, W-P. and S. Ntafos, Shortest watchman routes in simple polygons, Discrete Comput. Geom., 6 (1991) 9-31.

Chvátal, V., A combinatorial theorem in plane geometry, JCT (B), 18 (1975) 39-41.

Czyzowicz, J. and E. Rivera-Campo, J. Urrutia, J. Zaks, Illuminating and guarding segments in the plane, Discr. Math., 137 (1995) 147-153.

De Berg, M. and M. van Kreveld, M. Overmans, O. Schwarzkopf, Polygon Triangulation: Guarding an Art Gallery, Chapter 3, in Computational Geometry: Algorithms and Applications, 2nd. rev. ed., Springer-Verlag, Berlin, 2000.

Deneen, L. and G. Shute, Polygonizations of point sets in the plane, Disc. and Comp. Geo., 3 (1988) 77-87,

Estivill-Castro, V. and J. O'Rourke, J. Urrutia, D. Xu, Illumination of polygons with vertex floodlights, Inform. Process. Lett., 56 (1995) 9-13.

Fejes-Tóth, L., Illumination of convex disks, Acta Math. Acad. Sci. Hungar., 29 (1977) 355-360.

Fekete, S., On simple polygonalizations with optimal area, Discrete and
Computational Geometry, 23 (2000) 73-110.

Fisk, S., A short proof of Chvátal's watchman theorem, JCT (B) 24 (1978) 374.

Gemignani, M., More on finite subsets and simple closed polygonal paths, Mathematics Magazine, 39 (1966) 158-160.

Gewali, L., Placing guards inside orthogonal polygons, Inform. Sci., 88 (1996) 1-14.

Gewali, L. and S. Ntafos, Cover grids and orthogonal polygons with periscope guards, Comput. Geom., 2 (1993) 309-334.

Ghosh, S., Approximation algorithms for art gallery problems, Proc. Canadian Inform. Process. Soc. Congress, 1987.

Goodman, J. and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton, 1997.

Greene, D., The decomposition of polygons into convex parts, In Advances in Computing Research, Vol. I., F. Preparata, (ed.),, JAI Press, Connecticut, 1983, p. 235-259.

Grünbaum, B., Hamiltonian polygons and polyhedra, Geombinatorics, 3 (1994) 83-89.

Gyõri, A short proof of the rectilinear art gallery theorem, SIAM J. Algebraic Discrete Methods, 7 (1986) 452-454.

Hershberger, J. and S. Suri, Finding a shortest diagonal of a simple polygon in linear time, Comput. Geom., 7 (1997) 149-160.

Hoffmann, F., On the rectilinear art gallery problem, ICALP 90 Automata, Languages and Programming, LNCS, Vol. 443, pp. 717-728, Springer, July 1990.

Honsberger, R., Mathematical Gems II, Mathematical Association of America, Washington, 1976, p. 104-110.

Kahn, J. and M. Klawe, D. Kleitman, Traditional galleries require fewer watchmen, SIAM J. Alg. Disc. Math., 4 (1993) 194-206.

Kalai, G. and J. Matousek, Guarding galleries where every point sees a large area, Israel J. Math., 101 (1997) 125-139.

Lee, D. and A. Lin, Computational Complexity of Art Gallery Problems, IEEE Transactions on Information Theory, Vol. 32, pp. 276-282, 1986.

Lennes, N., Theorems on the simple finite polygon and polyhedron, Amer. J. Math., 33 (1911) 36-62.

Lorenzetto, G. and A. Datta, R. Thomas, A fast trapezoidation technique for planar polygons, Computers & Graphics, 26 (2002) 281-289.

Lu, D-K. and F-R. Hus, C. Yi, Guarding in a simple polygon, Inform. Process. Lett., 75 (2000) 153.158.

Meisters, G., Polygons have ears, Amer. Math. Monthly 82 (1975) 648-651.

Meisters, G., Principal vertices, exposed points, and ears, American Mathematical Monthly. April 1980, 284-285.

Michael, T. and V. Pinciu, Art gallery theorems for guarded guards, Computational Geometry, 26 (2003) 247-258.

Mirzaian, A., Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Computational Geometry: Theory and Applications, 2 (1992) 15-30.

O'Rourke, J., Art Gallery Theorems and Algorithms, Oxford U. Press, New York, 1987.

O'Rourke, J. Computational geometry column 15, International J. of Computational Geometry and Its Applications 2 (1992) 215-217, (also, SIGACT News, 23 (1992) 26-28.)

O'Rourke, J. Computational geometry column 18, International J. of Computational Geometry and Its Applications 3 (1993) 107-113, (also, SIGACT News, 24 (1993) 20-25.)

O'Rourke, J., Computational Geometry in C (2nd ed.), Cambridge U. Press, New York, 1998.

O'Rourke, J., Visibility, in Handbook of Discrete and Computational Geometry, ed. J. Goodman and J. O'Rourke, CRC Press, Boca Raton, 1997, Chapter 25.

O'Rourke, J. and T. Shermer, I. Streinu, Illuminating convex polygons with vertex headlights, In Proc. 7th Canad. Conf. Comput. Geom., 1995, p. 151-156.

Preparata, F. and I. Shamos, Computational Geometry, Springer-Verlag, New York, 1985.

Przydtycki, J. and A. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Comb. Theory (A) 92 (2000) 68-76.

Sack, J., Rectilinear Computational Geometry, Ph. D. Thesis, School of Computer Science, McGill University, 1984.

Sack, J. and J. Urrutia, Handbook of Computational Geometry, Elsevier, Amsterdam, 1999.

Schuchardt, D. and H. Hecker. Two NP-hard art gallery problems for ortho-polygons, Math. Logistics Quarterly, 41 (1995) 261-267.

Seidel, R., A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry, 1 (1991) 51-64.

Shermer, T., Recent results in art galleries, Proc. IEEE, 80 (1992) 1384-1399.

Tóth, C., Illuminating both sides of line segments, in Discrete and Computational Geometry, J. Akiyama, M. Kano, and M. Urabe (eds.), Lecture Notes in Computer Science, 2098, Springer-Verlag, New York, 370-380.

Urabe, M. and M. Watanabe, On a counterexample to a conjecture of Mirzaian, Computational Geometry: Theory and Applications, 2 (1992) 51-53.

Urrutia, J., Art Gallery and Illumination Problems, in Handbook on Computational Geometry, J. Sac, and J. Urrutia, (eds.), Elsevier Science Publishers, Amsterdam, 2000, p. 973-1027.

Urrutia, J., Sixth proof of the orthogonal art gallery theorem (unpublished manuscript).

Valtr, P., Guarding galleries where no point sees a small area, Israel J. Math., 104 (1998) 1-16.

Viswanathan, S., Tight bounds for the number of edge guards for spiral polygons, J. Geom., 51 (1994) 178-186.

Zalik, B. and G. Clapworthy, A universal trapezoidation algorithm for planar polygons, Computers & Graphs, 23 (1999) 353-363.

Zalik, B. and A. Jezernik, K. Zalik, Polygon trapezoidation by sets of open trapezoids, Computers & Graphics, 27 (2003) 791-800.

Note:

The Association for Computing Machines via its special interest groups for Graphics and Algorithms and Computation Theory sponsors an annual meeting on Computational Geometry. The proceedings of this conference has been published every year since the first conference was held in 1985. Papers in these volumes can be accessed via the ACM Portal.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials.