La conocida galería de arte problema se inicia con una "galería de arte" (un simple polígono en el plano, no necesariamente convexa) y pide el número mínimo de "guardias" (puntos en el polígono), necesarios para "observar la galería completa" (que tienen la propiedad de que para cualquier punto en el interior del polígono, hay un segmento de línea que apuntan a un "guardia" que se encuentra en su totalidad dentro del polígono). Chvatal mostró que si el polígono tiene $n$ vértices, a continuación, $\lfloor n/3\rfloor$ guardias son suficientes, y a veces necesario, para observar toda la galería.
Si usted se olvida de tratar de minimizar el número de guardias, y simplemente quiere poner guardias para que ellos puedan ver la galería completa, es razonablemente claro que si se coloca un guardia en cada vértice de un polígono simple, van a ser capaces de observar toda la galería.
Una forma de ver esto es para nota, que la afirmación es clara para los triángulos, y luego de recordar (o convencer a uno mismo) que cualquier simple polígono puede ser triangulados sin añadir vértices.
Si la visualización de toda una triangulación de un polígono es demasiado "global", uno puede pensar en "local" de la siguiente manera. Arreglar cualquier punto de $p$, en la galería interior. Elija un punto de $q$ en el polígono tales que la distancia de $p$ $q$es mínimo. El segmento de la línea de $p$ $q$se encuentra dentro de la galería. Si $q$ es un vértice, hemos terminado. De lo contrario, $q$ está en el interior de un borde. Escoger una dirección en ese borde y mover $q$ a lo largo del borde en esa dirección. Finalmente, una de dos cosas va a suceder: (1) el punto de $q$ se convierte en un vértice, o (2) hay un primer momento en el que el segmento de la línea de $p$ $q$cruza el polígono en algún lugar, además de a $q$. En caso de que (1) hemos terminado, y en el caso (2), podemos convencernos de que en el momento en que esto sucede, el punto más cercano a $p$ en la intersección del polígono y el segmento de línea debe ser de un vértice, y estamos de nuevo por hacer.
Ahora cambiar a partir de dos dimensiones a tres, para una "galería de arte" ahora es un poliedro. Si lugar a un guardia en cada vértice, se puede ver la galería entera?
La respuesta, en general, es no.
Puede que no sea claro por qué es que no, pero es relativamente claro que los argumentos que se acaban de dar, no hay que generalizar en cualquier forma sencilla.
Hay poliedros que no puede ser "nidos" en tetraedros sin añadir vértices. Un famoso ejemplo de esto es el Schoenhardt poliedro. (Sin embargo: experimentando con este applet me convenció de que los vértices de este poliedro hacer ver todo su interior.)
El "da $p$, escoger un punto más cercano a $q$ en el poliedro, y, a continuación, mueva $q$ en alguna dirección" idea claramente no funciona (al menos sin juiciosa elección de la dirección), porque en el caso (2) no hay ninguna razón para que el punto más cercano de la intersección de la línea de segmento de $p$ $q$con el poliedro a ser un vértice en el caso tridimensional. Puede muy ser, obviamente, en el interior de un poco de borde.
Así que no es contrario a la intuición, a mí, que hay poliedro cuyos vértices no puede observar su interior. Pero me gustaría una mejor imagen mental de lo que un poliedro puede en realidad "." (Una mejor imagen, por ejemplo, de lo que me sale en la foto en la entrada de la Wikipedia para la galería de arte problema).
Puede alguien describir un poliedro, de tal manera que, en cierto sentido, "obvio" que sus vértices no puede ver todo su interior? De modo que es posible formar una clara imagen mental de lo que se vería como estar dentro de un poliedro, en un punto donde no puede ver los vértices? (¿ Qué ves?)
