Computational geometry

ABSTRACT

Recent solutions of three "art gallery" problems are reported. Three related still-open problems are discussed.

REFERENCES

• 1: [BSS91] I. Bjorling-Sachs and D. Souvaine. A tight bound for guarding general polygons with holes. Technical Report LCSR-TR-165, Rutgers University, Dept. of Computer Science, May 1991.
• 2: [Dor89] S. Dorward, 1989. Personal communication.
• 3: [FK92] Z. Füredi and D. Kleitman. The prison yard problem. Combinatorica, 1992. To appear.
• 4: Frank Hoffmann , Michael Kaufmann , Klaus Kriegel, The Art Gallery theorem for polygons with holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.39-48, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185346]
• 5: Frank Hoffmann, On the Rectilinear Art Gallery Problem (Extended Abstract), Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.717-728, July 16-20, 1990
• 6: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 7: [She92] T. Shermer. Recent results in art galleries. Proc. IEEE, 1992. To appear. Also Tech Report CMPT TR 90-10, Simon Fraser University, Computing Science, October 1990.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory