As with mobile guarding, edge guarding a simple polygon deals with edge visiblity. More precisely, given a polygon P of n vertices, what is the maximum number of edge guards required to cover P. We defined an edge guard quite simply as a guard patrolling an edge of P. Furthermore, to cover a polygon we require that for every point xP, that at least one guard can see point x. We consider a guard to be able to see a point x iff there exists a point y anywhere along the guards patrolling path (remember this is an edge of P) for which the straight line segment xy lies entirely within P.
Although this collection of web pages was prompted by an interest in edge guarding, I regret to inform the reader that, as of yet, the problem is still open. I've spent countless hours pouring over various approaches to the solving the problem to show thatn/4
edge guards are sufficient to cover any simple polygon of n vertices. However, I've not been able to put together a proof of this upper bound or a counter-example for it. It is interesting to note that in fact O'Rourke dedicated much effort towards solving the edge guarding problem but settled on putting forth his proof for mobile guards after being unable to do so.
This conjecture was first made by Toussaint who inspired this variant of the art gallery problem. Although Shermer and Page put forth two examples of polygons requireing
Although no solution has been put forth for the problem of edge garding, some results are still known. In fact O'Rourke himself showed that the approach he used in proving the result for mobile guards cannot be applied to find the same result for edge-guards. Quite simply, this is due to the fact that there exist classes of triangulations that cannot be dominated by
Shermer, however, by the same technique did indeed show that any polygon can covered by
gE(n)
[NEXT]