How many guards are needed to visually cover a polygonal art gallery? Fifty years ago, this simple question initiated a field that has blossomed into a rich body of work on variations, fueled by over 2,500 technical papers. Entrance to this captivating world has been difficult for the novice because of its vast scope and sometimes intricate proofs. Assuming only high-school geometry, this accessible introduction relies on geometric intuition. Over 100 color figures and thumbnail sketches of proof techniques enable beginners to follow and appreciate the proofs, many of which are quite beautiful. More than 50 exercises, each completely solved in an appendix, extend the text and allow readers to gauge their understanding. The field continues to grow and generate new questions at the frontier of mathematics, highlighted as "open problems" that might be resolved by ambitious readers. This introduction is ideal for undergraduate students and math enthusiasts alike.
Joseph O'Rourke is Olin Professor of Computer Science and Mathematics Emeritus at Smith College. He has published over 175 papers in computational geometry. His awards include a Guggenheim Fellowship, the NSF Director's Award for Distinguished Teaching Scholars, and election as an ACM Fellow. This is his tenth book (four coauthored).
Preface; 1. The art gallery theorem; 2. Polygon triangulation; 3. Visibility in polygons; 4. Minimal guard coverage; 5. Orthogonal polygons; 6. 3D; 7. Visibility variations; 8. k-visibility; 9. Mirror polygons; A. Solutions to exercises; B. List of symbols; Bibliography; Index.
How many guards are needed to visually cover a polygonal art gallery? Fifty years ago, this simple question initiated a field that has blossomed into a rich body of work on variations, fueled by over 2,500 technical papers. Entrance to this captivating world has been difficult for the novice because of its vast scope and sometimes intricate proofs. Assuming only high-school geometry, this accessible introduction relies on geometric intuition. Over 100 color figures and thumbnail sketches of proof techniques enable beginners to follow and appreciate the proofs, many of which are quite beautiful. More than 50 exercises, each completely solved in an appendix, extend the text and allow readers to gauge their understanding. The field continues to grow and generate new questions at the frontier of mathematics, highlighted as "open problems" that might be resolved by ambitious readers. This introduction is ideal for undergraduate students and math enthusiasts alike.
Joseph O'Rourke is Olin Professor of Computer Science and Mathematics Emeritus at Smith College. He has published over 175 papers in computational geometry. His awards include a Guggenheim Fellowship, the NSF Director's Award for Distinguished Teaching Scholars, and election as an ACM Fellow. This is his tenth book (four coauthored).
Preface; 1. The art gallery theorem; 2. Polygon triangulation; 3. Visibility in polygons; 4. Minimal guard coverage; 5. Orthogonal polygons; 6. 3D; 7. Visibility variations; 8. k-visibility; 9. Mirror polygons; A. Solutions to exercises; B. List of symbols; Bibliography; Index.