''Art Gallery Theorems and Algorithms'' is a mathematical monograph on topics related to the

art gallery problem The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: In the geometric version of the problem, the layout of the art gallery is represent ...

, on finding positions for guards within a polygonal museum floorplan so that all points of the museum are visible to at least one guard, and on related problems in computational geometry concerning

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed '' polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two t ...

s. It was written by Joseph O'Rourke, and published in 1987 in the International Series of Monographs on Computer Science of the

Oxford University Press Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print book ...

. Only 1000 copies were produced before the book went out of print, so to keep this material accessible O'Rourke has made a pdf version of the book available online.

Topics

The

, posed by

Victor Klee Victor LaRue Klee, Jr. (September 18, 1925 – August 17, 2007) was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of ...

in 1973, asks for the number of points at which to place guards inside a polygon (representing the floor plan of a museum) so that each point within the polygon is visible to at least one guard.

Václav Chvátal Václav (Vašek) Chvátal () is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada and a Visiting Professor at Charles University in Prague. He has published ext ...

provided the first proof that the answer is at most

\lceil n/3\rceil

for a polygon with

n

corners, but a simplified proof by Steve Fisk based on

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

and

polygon triangulation In computational geometry, polygon triangulation is the partition of a polygonal area ( simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may ...

is more widely known. This is the opening material of the book, which goes on to covers topics including

visibility The visibility is the measure of the distance at which an object or light can be clearly discerned. In meteorology it depends on the transparency of the surrounding air and as such, it is unchanging no matter the ambient light level or time of ...

, decompositions of polygons, coverings of polygons, triangulations and triangulation algorithms, and higher-dimensional generalizations, including the result that some

polyhedra In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on t ...

such as the

Schönhardt polyhedron In geometry, the Schönhardt polyhedron is the simplest non-convex polyhedron that cannot be triangulated into tetrahedra without adding new vertices. It is named after German mathematician Erich Schönhardt, who described it in 1928. The same ...

do not have triangulations without additional vertices. More generally, the book has as a theme "the interplay between discrete and computational geometry". It has 10 chapters, whose topics include the original art gallery theorem and Fisk's triangulation-based proof;

rectilinear polygon A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons. In many cases another definition is ...

s; guards that can patrol a line segment rather than a single point; special classes of polygons including

star-shaped polygon In geometry, a star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible. Formally, a polygon is star-shaped if there exists a poi ...

s, spiral polygons, and

monotone polygon In geometry, a polygon ''P'' in the plane is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects the boundary of ''P'' at most twice. Similarly, a polygonal chain ''C'' is called monotone with respe ...

s; non-simple polygons; prison yard problems, in which the guards must view the exterior, or both the interior and exterior, of a polygon;

visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge rep ...

s; visibility algorithms; the

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of minimizing the number of guards; and three-dimensional generalizations.

Audience and reception

The book only requires an undergraduate-level knowledge of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

and

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s. However, it lacks exercises, and is organized more as a monograph than as a textbook. Despite warning that it omits some details that would be important to implementors of the algorithms that it describes, and does not describe algorithms that perform well on random inputs despite poor worst-case complexity, reviewer Wm. Randolph Franklin recommends it "for the library of every geometer". Reviewer

Herbert Edelsbrunner Herbert Edelsbrunner (born March 14, 1958) is a computer scientist working in the field of computational geometry, the Arts & Science Professor of Computer Science and Mathematics at Duke University, Professor at the Institute of Science and Techn ...

writes that "This book is the most comprehensive collection of results on polygons currently available and thus earns its place as a standard text in computational geometry. It is very well written and a pleasure to read." However, reviewer Patrick J. Ryan complains that some of the book's proofs are inelegant, and reviewer

David Avis David Michael Avis (born March 20, 1951) is a Canadian and British computer scientist known for his contributions to geometric computations. Avis is a professor in computational geometry and applied mathematics in the School of Computer Scienc ...

, writing in 1990, noted that already by that time there were "many new developments" making the book outdated. Nevertheless, Avis writes that "the book succeeds on a number of levels", as an introductory text for undergraduates or for researchers in other areas, and as an invitation to solve the "many unsolved questions" remaining in this area.

References

{{reflist, refs= {{citation , last = Avis , first = David , authorlink = David Avis , doi = 10.1090/S0273-0979-1990-15939-7 , issue = 1 , journal = American Mathematical Society , mr = 1567872 , pages = 230–234 , series = New Series , title = Review of ''Art Gallery Theorems and Algorithms'' , volume = 23 , year = 1990, doi-access = free {{citation, title=Review of ''Art Gallery Theorems and Algorithms'', journal=Mathematical Reviews, first=Herbert, last=Edelsbrunner, authorlink=Herbert Edelsbrunner, year=1989, mr=0921437 {{citation , last = Franklin , first = Wm. Randolph , date = June 1989 , doi = 10.1137/1031076 , issue = 2 , journal = SIAM Review , pages = 342–343 , title = Review of ''Art Gallery Theorems and Algorithms'' , volume = 31 {{citation, first=M., last=Vlach, title=Review of ''Art Gallery Theorems and Algorithms'', journal=zbMATH, zbl=0653.52001 {{citation, first=Patrick J., last=Ryan, journal=ACM Computing Reviews, title=Review of ''Art Gallery Theorems and Algorithms'', url=https://dl.acm.org/doi/10.5555/40599 {{citation, url=http://cs.smith.edu/~jorourke/books/ArtGalleryTheorems/art.html, first=Joseph, last=O'Rourke, authorlink=Joseph O'Rourke (professor), title=Art Gallery Theorems and Algorithms, publisher=Smith College, accessdate=2020-02-20 Computational geometry Polygons Mathematics books 1987 non-fiction books