Art Gallery Theorems and Algorithms

Art gallery theorems and algorithms are so called because they relate to problems involving the visibility of geometrical shapes and their internal surfaces. This book explores generalizations and specializations in these areas.

**Tag(s):**
Algorithms and Data Structures

**Publication date**: 31 Dec 1987

**ISBN-10**:
0195039653

**ISBN-13**:
n/a

**Paperback**:
304 pages

**Views**: 15,617

Art Gallery Theorems and Algorithms

Art gallery theorems and algorithms are so called because they relate to problems involving the visibility of geometrical shapes and their internal surfaces. This book explores generalizations and specializations in these areas.

Book Description at Amazon.com:

Excerpts from the Preface:

Art gallery theorems and algorithms are so called because they relate to problems involving the visibility of geometrical shapes and their internal surfaces. This book explores generalizations and specializations in these areas. Among the presentations are recently discovered theorems on orthogonal polygons, polygons with holes, exterior visibility, visibility graphs, and visibility in three dimensions. The author formulates many open problems and offers several conjectures, providing arguments which may be followed by anyone familiar with basic graph theory and algorithms. This work may be applied to robotics and artificial intelligence as well as other fields, and will be especially useful to computer scientists working with computational and combinatorial geometry.

Excerpts from the Preface:

Joseph O'Rourke wrote:This book is a research monograph on a topic that falls under both combinatorial geometry, a branch of mathematics, and computational geometry, a branch of computer science. The research described is recent: the earliest dates from the mid 1970s, and the majority is from the 1980s. Many of the results discussed have not yet been published. Advances continue to be made, especially on the algorithms side of the topic, and I have suffered the frustration of seeing each draft grow out of date before it was completed. Although the area of art gallery theorems has not stabilized, I believe the time is ripe for a survey, for two reasons.

First, the material is fascinating and accessible, and should be made available to a wider audience. Although this monograph is not a traditional textbook (there are no exercises, for example), I have used some of the material to great effect in a graduate/undergraduate course on computational geometry. The only prerequisites for understanding the material are basic graph theory, data structures, and algorithms. Thus it is easily accessible to upper-level undergraduates, or indeed to the "amateur." I have found that students can become very excited at finding themselves so quickly at the frontier of knowledge, with a chance of extending the frontier themselves (and several of mine have).

Second, I hope that this monograph will accelerate the maturing of the field by drawing attention to the many open problems. These consist of two types: finding more succinct proofs of the theorems, and proving or disproving the conjectures. There is a history in this field of proofs being drastically shortened after a few years, and I expect some of the more ungainly proofs in this book also will be similarly upstaged. The conjectures are certainly not all equally difficult. Some may be open only because no one has tried hard enough to settle them (edge guards?), some are open because they appear to be genuinely difficult (polygons with holes?), and some seem to await the new idea that will solve them in a single stroke (prison yard problem?). I will be disappointed if many of the unsolved problems posed in this book are not solved in the next decade.

Tweet

About The Author(s)

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors