×

An introduction to computational geometry by the Art Gallery Theorems. (Una introduccion a la geometria computacional a traves de los teoremas de la galeria de arte.) (Spanish) Zbl 0864.68068

The booklet under review represents a minicourse the aim of giving an introduction to computational geometry. This field should of course not be confused with the fruitfull subject of computational algebraic geometry.
Rather than presenting a broad and general survey of the main facets of this recent branch of geometry, the author focuses the attention on a rather thorough and careful study of a group of results referred to as the Art Gallery theorems.
The original art gallery theorem asserts that in order to guard a simple polygon with \(n\) vertices, \(\lfloor n/4\rfloor\) guards are always sufficient and occasionally necessary. A refined analysis leads to algorithms for triangulating polygons.
When the polygon is orthogonal, it is shown that the number of guards can be reduced \(\lfloor n/4\rfloor\). Further subjects include the visibility graph of a polygon, and partial results toward the still open problem of characterizing visibility graphs.
Assuming very little in terms of preliminaries, the author excellently attains his goal of giving an introduction to an intrieging class of mathematical problems. The interplay between geometric and combinatorical concepts on one hand and algorithms and computations on the other is well suited as background for applications of mathematics in industry and technology.
Reviewer: A.Holme (Bergen)

MSC:

68R05 Combinatorics in computer science
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite