Illumination of Polygons

Table of contents

• Illuminating polygons with holes using vertex guards
• Shermer's open problem on illuminating orthogonal polygons with holes using vertex guards
• Hoffman's open problem on illuminating orthogonal polygons with holes using vertex guards
• Guarding a polygon with edge guards
• The prison yard problem for orthogonal polygons

Illuminating polygons with holes with vertex guards

The following conjecture is due to T. Shermer:

Conjecture: Any polygon with $$n$$ vertices and $$h$$ holes can always be illuminated with Floor[(n+h)/3] vertex guards.

Shermer's open problem on illuminating orthogonal polygons with holes using vertex guards

There are two conjectures on illuminating orthogonal polygons with holes. The oldest one is due to Tom Shermer. He conjectures:

Conjecture: Any orthogonal polygon with $$n$$ vertices and $$h$$ holes can always be illuminated with Floor[(n+h)/4] vertex guards.

Hoffman's open problem on illuminating orthogonal polygons with holes using vertex guards.

This is a conjecture that is similar to Shermer's problem on orthogonal polygons, however, they are not equivalent. Hoffman conjectures:

Conjecture: Floor[(2n)/7] vertex guards are always sufficient to guard any orthogonal polygon with holes.

Guarding a polygon with edge guards

A set of edges S guards a polygon $$P if every point in the interior of $$P sees at least one element of S.

The following was conjectured by G. Toussaint in 1983.

Conjecture: Except for a few polygons, floor[n/4] edge guards are always sufficient to guard any polygon $$P_n with n vertices.

The prison yard problem for orthogonal polygons

In the prison yard problem, we are required to guard simultaneously the interior and the exterior of a polygon. For arbitrary polygons this problem is closed. For orthogonal polygons, the problem remains open. The best upper bound known to date is due to Hoffman and Krieger, who showed that Floor[(5n)/12]+2 (resp. Floor[(n+4)/3]) vertex (resp. point) guards are always sufficient to guard the interior and the exterior of an orthogonal polygon with n vertices and holes. They also conjecture:

Conjecture : There is a constant c such that any orthogonal prison yard can be guarded with (5n)/16 + c vertex guards.

A la página principal de problemas abiertos . A mi página.