Illumination of sets of polygons.

Table of contents

Illuminating families of triangles on the plane

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.

A family of n triangles that requires n point lights.

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.

  1. Bjorling-Sachs, I., and D. Souvaine,"An efficient algorithm for guard placement in polygons with holes", Discrete and Computational Geometry 13, 77-109, 1995.

  2. Czyzowicz, J., E. Rivera-Campo, and J. Urrutia,"Illuminating rectangles and triangles on the plane", Journal of Combinatorial Theory B 57, 1-17, 1993.

  3. 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.

  4. 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.


Illuminating the free space of a family of quadrilaterals

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.

Czyzowicz and Urrutia's polygons.

  1. J. Garcia-Lopez,"Problemas algoritmico-combinatorios de visibilidad", Ph.D. Thesis, Universidad Politecnica de Madrid, (1995).

  2. 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.

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

A la página del Instituto de Matemáticas