The following conjecture is due to T. Shermer:
Conjecture: Any polygon with
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
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.
A set of edges S guards a polygon
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
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.
Jorge Urrutia,
Instituto de Matemáticas, Universidad Nacional Autónoma de México urrutia@matem.unam.mx |
School of Information Technology and Engineering University of Ottawa, jorge@site.uottawa.ca |