The following conjecture is due to Czyzowicz, Rivera-Campo, and Urrutia:
Conjecture There is a constant c such that n+c point lights are sufficient to illuminate any collection of n triangles.
The best upper bound known to date is Floor[4n/3] [2, 4]. This follows from the recent result that any polygon with n vertices containing holes can always be illuminated with Floor[n/3] point guards [1, 3]. For homothetic triangles, it is known that n+1 lights are always sufficient, and n sometimes necessary.
Bjorling-Sachs, I., and D. Souvaine,"An efficient algorithm for guard placement in polygons with holes", Discrete and Computational Geometry 13, 77-109, 1995.
Czyzowicz, J., E. Rivera-Campo, and J. Urrutia,"Illuminating rectangles and triangles on the plane", Journal of Combinatorial Theory B 57, 1-17, 1993.
Hoffman, F., and K. Kriegel,"A graph coloring result and its consequences for the polygon guarding problem", Technical report B 93-08, Freie Universitat Berlin.
Urrutia, J.,"Art Gallery and Illumination Problems", to appear in Handbook on Computational Geometry, J.R. Sack and J. Urrutia, eds. Elsevier Science Publishers, 1997.
The following problem was posed by Garcia-Lopez:
Problem Determine the minumum number of point guards necessary to illuminate the free space generated by a family of n disjoint quadrilaterals.
The free space generated by a family of disjoint quadrilaterals is the complement of their union. In [1], Garcia-Lopez conjectured that n+c points would always suffice. This was disproved by Czyzowicz and Urrutia [2] who gave an example of a n=3m-3 quadrilateral that requires 4m-4 point guards.J. Garcia-Lopez,"Problemas algoritmico-combinatorios de visibilidad", Ph.D. Thesis, Universidad Politecnica de Madrid, (1995).
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 |