Maths/Logic Question

[RancidYakButterTeaParty]

Any help is appreciated:

As we know Chvatal’s Art Gallery Theorem says that for a Gallery in the

shape of a simple polygon with n sides you never need more than

floor(n/3) guards to guard the walls. In illustrating its use we convert

to a graph by making the vertices be the corners of the polygon and the

edges be the walls. We then triangulate the graph by adding edges

internally that subdivide the interior of the gallery into triangular

regions.

The actual number of guards needed then is a function not only of the

shape of the gallery but also the manner in which a student triangulates.

Has there been any recent progress on methods of triangulation that will

optimize (minimize) the number of guards?

[Tyrrell_McAllister]

A search on scholar.google.com turned up a link to this paper:

Guarding polyhedral terrains, by Prosenjit Bosea, Thomas Shermer, Godfried Toussaint, and Binhai Zhu.

Abstract

We prove that floor(n/2) floor vertex guards are always sufficient and sometimes necessary to guard the surface of an n-vertex polyhedral terrain. We also show that floor((4n − 4)/13) edge guards are sometimes necessary to guard the surface of an n-vertex polyhedral terrain. The upper bound on the number of edge guards is floor(n/3) (Everett and Rivera-Campo, 1994). Since both upper bounds are based on the four color theorem, no practical polynomial time algorithm achieving these bounds seems to exist, but we present a linear time algorithm for placing floor(3n/5) vertex guards for covering a polyhedral terrain and a linear time algorithm for placing floor(2n/5) edge guards.

Author Keywords: Polyhedral terrains; Art gallery theorems; Matching