Conjunto opaco

Si${\displaystyle K}$Si se trata de un conjunto convexo acotado que se va a cubrir, entonces su frontera${\displaystyle \partial K}$forma un conjunto opaco cuya longitud es el perímetro${\displaystyle |\partial K|}$Por lo tanto, la longitud más corta posible de un conjunto opaco es como máximo el perímetro. Para conjuntos${\displaystyle K}$que son estrictamente convexos, lo que significa que no hay segmentos de línea en el límite, y para barreras interiores, este límite es ajustado. Cada punto en el límite debe estar contenido en el conjunto opaco, porque cada punto del límite tiene una línea tangente que pasa por él que no puede ser bloqueada por ningún otro punto. ^{[ 5 ]} El mismo razonamiento muestra que para barreras interiores de polígonos convexos , todos los vértices deben estar incluidos. Por lo tanto, el árbol de Steiner mínimo de los vértices es el conjunto opaco conectado más corto , y la trayectoria del viajante de comercio de los vértices es el conjunto opaco de una sola curva más corto . ^{[ 4 ]} Sin embargo, para barreras interiores de conjuntos convexos no poligonales que no son estrictamente convexos, o para barreras que no se requiere que estén conectadas, otros conjuntos opacos pueden ser más cortos; por ejemplo, siempre es posible omitir el segmento de línea más largo del límite. En estos casos, el perímetro o la longitud del árbol de Steiner proporcionan un límite superior en la longitud de un conjunto opaco. ^{[ 3 ] [ 4 ]}

Hay varias pruebas de que un conjunto opaco para cualquier conjunto convexo${\displaystyle K}$debe tener una longitud total al menos${\displaystyle |\partial K|/2}$, la mitad del perímetro. Una de las más sencillas implica la fórmula de Crofton , según la cual la longitud de cualquier curva es proporcional a su número esperado de puntos de intersección con una línea aleatoria de una distribución de probabilidad apropiada sobre líneas. Es conveniente simplificar el problema aproximando${\displaystyle K}$por un superconjunto estrictamente convexo, que puede elegirse de modo que su perímetro sea arbitrariamente cercano al conjunto original. Entonces, excepto por las líneas tangentes a${\displaystyle K}$(que forman una fracción ínfima de todas las líneas), una línea que interseca${\displaystyle K}$cruza su límite dos veces. Por lo tanto, si una línea aleatoria interseca${\displaystyle K}$con probabilidad${\displaystyle p}$, el número esperado de cruces de frontera es${\displaystyle 2p}$. Pero cada línea que se cruza${\displaystyle K}$interseca su conjunto opaco, por lo que el número esperado de intersecciones con el conjunto opaco es al menos${\displaystyle p}$, que es al menos la mitad de eso para${\displaystyle K}$Según la fórmula de Crofton, las longitudes del límite y la barrera guardan la misma proporción que estos números esperados. ^{[ 6 ]}

Este límite inferior de${\displaystyle |\partial K|/2}$La longitud de un conjunto opaco no se puede mejorar para tener un factor constante mayor que 1/2, porque existen ejemplos de conjuntos convexos que tienen conjuntos opacos cuya longitud es cercana a este límite inferior. En particular, para rectángulos delgados muy largos, un lado largo y dos lados cortos forman una barrera, con una longitud total que puede hacerse arbitrariamente cercana a la mitad del perímetro. Por lo tanto, entre los límites inferiores que consideran solo el perímetro de la región de cobertura, el límite de${\displaystyle |\partial K|/2}$es lo mejor posible. ^{[ 6 ]} Sin embargo, acercarse a${\displaystyle |\partial K|/2}$De esta manera se implica considerar una secuencia de formas en lugar de una sola forma, porque para cualquier conjunto convexo${\displaystyle K}$eso no es un triángulo, existe un${\displaystyle \delta }$de tal manera que todos los conjuntos opacos tengan una longitud al menos${\displaystyle |\partial K|/2+\delta }$. ^{[ 7 ]}

Para un triángulo , como para cualquier polígono convexo, el conjunto opaco conectado más corto es su árbol de Steiner mínimo. ^{[ 8 ]} En el caso de un triángulo, este árbol se puede describir explícitamente: si el ángulo más ancho del triángulo es${\displaystyle 2\pi /3}$(120°) o más, utiliza los dos lados más cortos del triángulo, y en caso contrario consiste en tres segmentos de línea desde los vértices hasta el punto de Fermat del triángulo. ^{[ 9 ]} Sin embargo, sin asumir conectividad, no se ha demostrado la optimalidad del árbol de Steiner. Izumi ha demostrado una pequeña mejora en la cota inferior de reducción a la mitad del perímetro para el triángulo equilátero . ^{[ 10 ]}

Para un cuadrado unitario , el perímetro es 4, el perímetro menos el lado más largo es 3, y la longitud del árbol de Steiner mínimo es${\displaystyle 1+{\sqrt {3}}\approx 2.732}$Sin embargo, se conoce un bosque opaco más corto y desconectado, con una longitud${\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}$Consiste en el árbol de Steiner mínimo de tres de los vértices del cuadrado, junto con un segmento de línea que conecta el cuarto vértice con el centro. Ross Honsberger atribuye su descubrimiento a Maurice Poirier, un maestro de escuela canadiense, ^{[ 11 ]} pero ya fue descrito en 1962 y 1964 por Jones. ^{[ 12 ] [ 13 ]} Se sabe que es óptimo entre los bosques con solo dos componentes, ^{[ 5 ] [ 14 ]} y se ha conjeturado que es el mejor posible en general, pero esto sigue sin probarse. ^{[ 7 ]} La cota inferior de 2 para la reducción a la mitad del perímetro del cuadrado, ya probada por Jones, ^{[ 12 ] [ 13 ]} puede mejorarse ligeramente, a${\displaystyle 2.00002}$, para cualquier barrera que consta de como máximo una cantidad numerable de curvas rectificables , ^{[ 7 ]} mejorando límites previos similares que restringían la barrera a colocarse solo cerca del cuadrado dado. ^{[ 6 ]}

El caso del círculo unitario fue descrito en una columna de Scientific American de 1995 por Ian Stewart , con una solución de longitud${\displaystyle 2+\pi }$[ ^{15 ]} óptimo para una sola curva o barrera conectada ^{[ 8 ] [ 16 ] [ 17 ]} pero no para un bosque opaco con múltiples curvas. Vance Faber y Jan Mycielski atribuyen esta solución de una sola curva a Menachem Magidor en 1974. ^{[ 8 ] Para 1980, E. Makai ya había proporcionado una mejor solución de} tres componentes, con una longitud aproximada${\displaystyle 4.7998}$, ^{[ 18 ]} redescubierto por John Day en una continuación de la columna de Stewart. ^{[ 19 ]} La longitud desconocida de la solución óptima se ha denominado constante de detección del haz . ^{[ 20 ]}

Según los límites generales para la longitud de bosques opacos en términos de perímetro, el perímetro de un conjunto convexo se aproxima a su bosque opaco más corto con una precisión de un factor de dos en longitud. En dos artículos, Dumitrescu, Jiang, Pach y Tóth proporcionan varios algoritmos de aproximación en tiempo lineal para el conjunto opaco más corto para polígonos convexos, con mejores índices de aproximación que dos:

• Para conjuntos opacos generales, proporcionan un algoritmo cuya razón de aproximación es como máximo$${\displaystyle {\frac {1}{2}}+{\frac {2+{\sqrt {2}}}{\pi }}\approx 1.5868.}$$La idea general del algoritmo es construir una barrera tipo "arco y flecha" a partir del cuadro delimitador de perímetro mínimo de la entrada, que consiste en una cadena poligonal que se extiende alrededor del polígono desde una esquina del cuadro delimitador hasta la esquina opuesta, junto con un segmento de línea que conecta una tercera esquina del cuadro delimitador con la diagonal del mismo. ^{[ 4 ]}
• Para conjuntos opacos que constan de un solo arco, proporcionan un algoritmo cuya razón de aproximación es como máximo$${\displaystyle {\frac {\pi +5}{\pi +2}}\approx 1.5835.}$$La barrera resultante se define mediante una línea de soporte de la forma de entrada. La entrada se proyecta perpendicularmente sobre un intervalo de esta línea, y la barrera conecta los dos extremos de este intervalo mediante una curva en forma de U que se ajusta firmemente alrededor de la entrada, como la barrera conectada óptima para un círculo. El algoritmo utiliza calibradores giratorios para encontrar la línea de soporte para la cual se minimiza la longitud de la barrera resultante. ^{[ 4 ]}
• Para conjuntos opacos conectados, proporcionan un algoritmo cuya razón de aproximación es como máximo${\displaystyle 1.5716}$Este método combina la barrera de arco único con un tratamiento especial para formas que están cerca de un triángulo equilátero , para el cual el árbol de Steiner del triángulo es una barrera conectada más corta. ^{[ 4 ]}
• Para barreras interiores, proporcionan un algoritmo cuya razón de aproximación es como máximo${\displaystyle 1.7168}$. ^{[ 24 ]} La idea es utilizar una generalización sugerida por Shermer de la estructura de los algoritmos anteriores incorrectos (un árbol de Steiner en un subconjunto de los puntos, junto con segmentos de altura para una triangulación de la entrada restante), ^{[ 23 ]} con una aproximación rápida para la parte del árbol de Steiner de la aproximación. ^{[ 24 ]}

Además, debido a que la barrera interior conectada más corta de un polígono convexo viene dada por el árbol de Steiner mínimo, tiene un esquema de aproximación de tiempo polinomial . ^{[ 4 ]}

La región cubierta por un determinado bosque se puede determinar de la siguiente manera:

• Encuentra la envoltura convexa de cada componente conexa del bosque.
• Para cada vértice${\displaystyle p}$del casco, traza una línea circular alrededor${\displaystyle p}$, subdividiendo el plano en cuñas dentro de las cuales la línea de barrido cruza uno de los cascos y cuñas dentro de las cuales la línea de barrido cruza el plano sin obstrucción. La unión de las cuñas cubiertas forma un conjunto${\displaystyle C_{p}}$.
• Encuentra la intersección de todos los conjuntos.${\displaystyle C_{p}}$Esta intersección es la cobertura del bosque.

Si la entrada consiste en${\displaystyle n}$segmentos de línea que se forman${\displaystyle m}$componentes conectados, luego cada uno de los${\displaystyle n}$conjuntos${\displaystyle C_{p}}$consta de como máximo${\displaystyle 2m}$cuñas. De ello se deduce que la complejidad combinatoria de la región de cobertura, y el tiempo para construirla, es${\displaystyle O(m^{2}n^{2})}$como se expresa en notación O grande . ^{[ 25 ]}

Aunque óptimo en el peor de los casos para entradas cuya región de cobertura tiene una complejidad combinatoria que coincide con este límite, este algoritmo puede mejorarse heurísticamente en la práctica mediante una fase de preprocesamiento que fusiona pares superpuestos de envolventes hasta que todas las envolventes restantes sean disjuntas, en el tiempo${\displaystyle O(n\log ^{2}n)}$. Si esto reduce la entrada a un único casco, no es necesario ejecutar el algoritmo de barrido e intersección más costoso: en este caso el casco es la región de cobertura. ^{[ 26 ]}