Cámaras de vigilancia vs matemáticas

Reclusorio de máxima seguridad: cortesía de CISEN 2014

Reclusorio de máxima seguridad: cortesía de CISEN 2014

La vigilancia por medio de guardias o cámaras de vigilancia, es de suma importancia para salvaguardar lugares que son estratégicos para una  persona, grupos o corporaciones.

Es importante saber el número y localización de los guardias o cámaras, con el fin de controlar el área de vigilancia y optimizar recursos

La solución al problema anterior inicia en las  obras de arte expuestas en las galerías que tienen que ser vigiladas debido a su valor (en ocasiones invaluable). Para reducir los costos derivados de la vigilancia, es necesario tener los menos guardias posibles de tal forma que cada obra sea vigilada por al menos un guardia. Esto se conoce como problemas de Galería de Arte y fue propuesto por vez primera por Víctor Kleen en 1973, quien formuló la siguiente pregunta:

¿Cuántos guardias son suficientes para vigilar las obras de arte en una galería con n paredes?

Los problemas de galería de arte, han sido de gran interés en geometría computacional y combinatoria desde la aparición del artículo de Chvátal en 1975, en el cual Chvátal prueba que  \left\lfloor\displaystyle\frac{n}{3}\right\rfloor guardias son siempre suficientes para vigilar un polígono simple con n vértices. Después de la aparición de este artículo, diversas variaciones han aparecido en la literatura, entre estas se encuentran, vigilar polígonos ortogonales, polígonos con hoyos, usar guardias móviles, etcétera.

* Donde  \lfloor m\rfloor=max\{k\in\mathbb{Z}:k\leq m\}

Los problemas de galería de arte son importantes en ciertas aplicaciones en ciencias de la computación, debido a que estos son fundamentalmente problemas de visibilidad y la visibilidad es de suma importancia en muchas aplicaciones computacionales. Algunas áreas de aplicación para visibilidad incluyen: robótica, planeación de movimiento, visión computacional, gráficas por computadora, reconocimiento de patrones, comunicaciones, entre otras.

Conceptos:

  • Polígono \mathcal{P}.
  • Decimos que un polígono \mathcal{P} esta particionado, si el interior del polígono está dividido en subpolígonos disjuntos. Si todos los subpolígonos son triángulos, decimos que \mathcal{P}  esta triangulado. Si todos los subpolígonos son cuadriláteros, decimos que \mathcal{P} esta cuadrilaterizado.
  • Guardias o cámaras en los vértices. Los guardias se localizan en vértices de \mathcal{P}. En adelante, cuando no se mencione lo contrario los guardias serán de esta clase.
  • Guardias en puntos. Los guardias pueden ser posicionados en cualquier punto dentro o en la frontera de \mathcal{P}.
  • Guardias en las aristas. Esta variante fue introducida por Toussaint en 1981. La principal motivación es permitirles a los guardias desplazarse sobre las aristas de \mathcal{P}. En el contexto de iluminación, esta puede considerarse como una lámpara fluorescente colocada en una arista de \mathcal{P}. En este caso la lámpara se considera del tamaño de la arista.
  • Guardias móviles.  Esta variante fue introducida por O’Rourke en1983, en esta versión, se permite que los guardias se desplazen sobresegmentos de línea contenidos en \mathcal{P}. Si sólo se permite que los guardias se desplazen sobre aristas y diagonales, estos son llamados guardias diagonales.
  • Reflectores en vértices y puntos. Los reflectores fueron introducidos por Urrutia en 1990. La principal motivación es que los guardias o dispositivos de vigilancia, tales como cámaras, tienen un ángulo de visibilidad limitado. Un reflector es una fuente de luz la cual ilumina con un ángulo restringido \alpha y puede ser rotado sobre su ápice. El ápice de los reflectores puede localizarse en los vértices o en puntos de cualquier parte de \mathcal{P}.

Antes de enunciar  el resultado principal de Chvátal; mostrare un resultado que a mi parecer es fundamental en este resultado y en muchos más de la geometría computacional.

Resultado 01. Cualquier polígono \mathcal{P} con n vértices admite una triangulación y cualquier triangulación consiste exactamente de n-2 triángulos.

gall03

Triangulación

Prueba. Probaremos la primer parte del teorema inductivamente sobre n. Cuando n=3, el pológono es un triángulo y el teorema es trivialmente cierto. Mostraremos que si \mathcal{P} tiene más de tres vértices, entonces siempre existe una diagonal que divide al polígono en dos subpolígonos, por lo que inductivamente se obtiene el resultado deseado.

Sea v el vértice más a la izquierda de \mathcal{P} y sean u y w los vértices de \mathcal{P} adyacentes a v. Si el segmento uw es una diagonal, entonces uw es la diagonal buscada.

Suponemos que uw no es una diagonal, por lo que el triángulo uvw contiene al menos un vértice del polígono. Tomemos el vértice x de \mathcal{P} en el interior de uvw más alejado del segmento uw. Por construcción, el segmento vx es la diagonal buscada; ver figura.

Para demostrar que una triangulación consiste de exactamente n-2 triángulos, considere cualquier diagonal arbitraria en alguna triangulación T de \mathcal{P}. Esta diagonal corta el polígono \mathcal{P} en dos subpolígonos con m_{1} y m_{2} vértices respectivamente, cada vértice de \mathcal{P} ocurre en alguno de los dos subpolígonos, excepto para los vértices de la diagonal, los cuales ocurren en ambos subpolígonos. Por lo que  m_{1}+m_{2}=n+2. Inductivamente, cualquier triangulación de los subpolígonos consiste de m_{i}-2 triángulos, lo que implica que

(m_{1}- 2)+(m_{2}-2)=n-2

El resultado en cual está centrado este post es el siguiente

Teorema (Chvátal)  \left\lfloor\displaystyle\frac{n}{3}\right\rfloor guardias son suficientes y ocasionalmente necesarios para vigilar el interior de cualquier galería de arte con n vértices.

gall004

El teorema nos da el número suficiente y ocasionalmente necesario de guardias para vigilar cualquier polígono con n vértices, sin embargo, muchos de los polígonos pueden vigilarse con menos de \left\lfloor\displaystyle\frac{n}{3}\right\rfloor. En 1979, Lee y Lin probaron que el problema de encontrar el mínimo número de guardias necesarios para vigilar un polígono es NP-completo. Hasta este momento las galerías de arte se han considerado como una construcción sin obstáculos (tales como pilares, paredes, etc.), en su interior. Si permitimos que la galería contenga obstáculos, entonces el polígono que lo representa contendrá hoyos, es decir, otros polígonos en la parte interior del polígono principal y \left\lfloor\displaystyle\frac{n}{3}\right\rfloor guardias no son suficientes para vigilar todo su interior. En 1984, Shermer mostró que cualquier polígono con un hoyo puede vigilarse con \left\lfloor\displaystyle\frac{n+1}{3}\right\rfloor guardias, la cota es justa. En 1991, dos pruebas independientes y totalmente diferentes fueron obtenidas para probar que \left\lfloor\displaystyle\frac{n+h}{3}\right\rfloor guardias en puntos son suficiente para vigilar cualquier galería con h hoyos, una prueba fue propuesta por Hoffman, Kaufman y Kriegel  y la otra por Sachs y Souvaine.

gall01

Galería con huecos

Finalmente el tener vigilado polígonos nos lleva a vigilar poliedros, seguramente en un futuro muy cercano hablare de dicho tema; mientras podemos pensar como burlar la vigilancia de las cámaras, ya se tiene el modelo matemático y las ideas principales para realizar tal hazaña.

Bibliografía

1- Václav Chvatal, A Combinatorial Theorem in Plane Geometry, Journal of Computorial Theory (B) 18, pp 39-41, 1975.

2.- Steve Fisk, A Short Proof of Chvatal’s Watchman Theorem, Journal of Combinatorial Theory, Series B 24, pp 374, 1978.

3.- Martin Aigner, Günter M. Ziegler, El libro de las demostraciones, Nivola, 2005.

4.- J. O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, London, New York, 1987.

5.- Joseph Malkevitch, Diagonals (parts I, II), Feature Column (AMS)

6.- J. Kahn, M. Klawe, and D. Kleitman, Traditional Galleries Require Fewer Watchmen, SIAM J. Alg. Disc. Meth., Vol 4, No. 2, pp 194-206, 1983.

7. T. Shermer Recent Results in Art GalleriesProceedings of the IEEE, vol. 80, 9, pp. 1384-1399, 1992.

8. Hemanshu Kaul, The art galley problem (conferencia)

Anuncios

Un comentario en “Cámaras de vigilancia vs matemáticas

  1. Pingback: - vigilesunegocio

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s