DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 07-1 Art Gallery Theorems and Triangulations

Date prepared: January 3, 2007

T. S. Michael United States Naval Academy Annapolis, MD 21402 email: tsm@usna.edu

Val Pinciu Southern Connecticut State University New Haven, CT 06515 email: pinciuv1@southernct.edu

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                       Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, Georgia Institute of Technology, HP Labs, IBM Research, Microsoft Research,

Rensselaer Polytechnic Institute, and Stevens Institute of Technology.

Module Description Information

• Title:

Art Gallery Theorems and Triangulations

• Authors:

T. S. Michael, United States Naval Academy Val Pinciu, Southern Connecticut State University

• Abstract:

The Art Gallery Problem asks for the maximum number of guards required to protect a polygonal art gallery with n walls. Fisk’s beautiful solution of the problem relies on elementary ideas from geometry (triangulations of polygons) and graph theory (vertex colorings). We discuss this background in detail and then present Fisk’s proof. We also explain how a similar coloring strategy was used to treat orthogonal art galleries—those whose walls meet at right angles.

• Informal Description:

How many stationary guards are need to protect an art gallery? We assume the floorplan of the gallery is any polygon with n sides. This geometric problem can be solved using notions from elementary graph theory. Exercises are sprinkled throughout the module to reinforce ideas. More substantial problems occur at the end of the module. An annotated bibliography directs the reader to further resources.

• Target Audience:

This module is aimed at junior and senior mathematics and computer science majors taking a course in combinatorics or graph theory.

• Prerequisites:

The module assumes some familiarity with mathematical induction and basic notions of graph theory.

• Mathematical Field:

Graph Theory, Computational Geometry

• Applications Areas:

Art gallery theorems are studied in computational geometry, a branch of mathematics with applications in such diverse areas such as computer vision, motion planning, and fingerprint identification methods.

• Mathematics Subject Classification:

05C15, 05C85, 68R10, 94C15

• Contact Information:

T. S. Michael Mathematics Department United States Naval Academy Annapolis, MD 21402 email: tsm@usna.edu

Val Pinciu Mathematics Department Southern Connecticut State University New Haven, CT 06515 email: pinciuv1@southernct.edu

• Other DIMACS modules related to this module:

Module 03–3: Security Cameras and Floodlight Illumination