Conjunto opaco

Forma que bloquea todas las líneas de visión.

Cuatro conjuntos opacos para un cuadrado unitario . Arriba a la izquierda: su límite, longitud 4. Arriba a la derecha: tres lados, longitud 3. Abajo a la izquierda: un árbol de Steiner de los vértices, longitud . Abajo a la derecha: la solución óptima conjeturada, longitud . ${\displaystyle 1+{\sqrt {3}}\approx 2.732}$ ${\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}$

En geometría discreta , un conjunto opaco es un sistema de curvas u otro conjunto en el plano que bloquea todas las líneas de visión a través de un polígono , círculo u otra forma. Los conjuntos opacos también se han denominado barreras , detectores de haz , cubiertas opacas o (en los casos en que tienen la forma de un bosque de segmentos de línea u otras curvas) bosques opacos . Los conjuntos opacos fueron introducidos por Stefan Mazurkiewicz en 1916, ^[1] y el problema de minimizar su longitud total fue planteado por Frederick Bagemihl en 1959. ^[2]

Por ejemplo, la visibilidad a través de un cuadrado unitario puede ser bloqueada por sus cuatro aristas límite, con longitud 4, pero un bosque opaco más corto bloquea la visibilidad a través del cuadrado con longitud . No está demostrado si este es el conjunto opaco más corto posible para el cuadrado, y para la mayoría de las otras formas este problema permanece igualmente sin resolver. El conjunto opaco más corto para cualquier conjunto convexo acotado en el plano tiene longitud como máximo el perímetro del conjunto, y al menos la mitad del perímetro. Para el cuadrado, se conoce un límite inferior ligeramente más fuerte que la mitad del perímetro. Otro conjunto convexo cuyos conjuntos opacos se estudian comúnmente es el círculo unitario , para el cual el conjunto opaco conexo más corto tiene longitud . Sin el supuesto de conectividad, el conjunto opaco más corto para el círculo tiene longitud como mínimo y como máximo . ${\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}$ ${\displaystyle 2+\pi }$ ${\displaystyle \pi }$ ${\displaystyle 4.7998}$

Varios algoritmos publicados que afirmaban encontrar el conjunto opaco más corto para un polígono convexo resultaron ser incorrectos. Sin embargo, es posible encontrar un conjunto opaco con una razón de aproximación garantizada en tiempo lineal , o calcular el subconjunto del plano cuya visibilidad está bloqueada por un sistema dado de segmentos de línea en tiempo polinomial .

Definiciones

Cada conjunto en el plano bloquea la visibilidad a través de un superconjunto de , su cobertura . consiste en puntos para los cuales todas las líneas que pasan por el punto intersecan . Si un conjunto dado forma un subconjunto de la cobertura de , entonces se dice que es un conjunto opaco , barrera , detector de haz o cobertura opaca para . Si, además, tiene una forma especial, que consiste en un número finito de segmentos de línea cuya unión forma un bosque , se llama bosque opaco . Hay muchos conjuntos opacos posibles para cualquier conjunto dado , incluido él mismo, y muchos bosques opacos posibles. Para los bosques opacos, o más generalmente para los sistemas de curvas rectificables , su longitud se puede medir de la manera estándar. Para conjuntos de puntos más generales, se puede utilizar la medida unidimensional de Hausdorff , y concuerda con la longitud estándar en los casos de segmentos de línea y curvas rectificables. ^[3] ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle K}$

La mayoría de las investigaciones sobre este problema suponen que el conjunto dado es un conjunto convexo . Cuando no es convexo sino simplemente un conjunto conexo , puede ser reemplazado por su envoltura convexa sin cambiar sus conjuntos opacos. Algunas variantes del problema restringen el conjunto opaco a estar completamente dentro o completamente fuera . En este caso, se llama barrera interior o barrera exterior , respectivamente. Cuando esto no se especifica, se supone que la barrera no tiene restricciones en su ubicación. También se han considerado versiones del problema en las que el conjunto opaco debe estar conectado o formar una sola curva. No se sabe si cada conjunto convexo tiene un conjunto opaco más corto, o si en cambio las longitudes de sus conjuntos opacos pueden acercarse a un ínfimo sin alcanzarlo nunca. ^[3] Cada conjunto opaco para puede aproximarse arbitrariamente en longitud por un bosque opaco, ^[4] y se ha conjeturado que cada polígono convexo tiene un bosque opaco como su conjunto opaco más corto, pero esto no se ha demostrado. ^[3] ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle P}$

Límites

Cuando la región a cubrir es un conjunto convexo , la longitud de su conjunto opaco más corto debe ser al menos la mitad de su perímetro y como máximo su perímetro. Para algunas regiones, se pueden realizar mejoras adicionales a estos límites.

Límite superior

Si es un conjunto convexo acotado que debe cubrirse, entonces su límite forma un conjunto opaco cuya longitud es el perímetro . Por lo tanto, la longitud más corta posible de un conjunto opaco es como máximo el perímetro. Para los conjuntos que son estrictamente convexos, lo que significa que no hay segmentos de línea en el límite, y para las barreras interiores, este límite es estricto. Cada punto del límite debe estar contenido en el conjunto opaco, porque cada punto del límite tiene una línea tangente que lo pasa y que no puede ser bloqueada por ningún otro punto. ^[5] El mismo razonamiento muestra que para las 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 conexo más corto, y el camino del vendedor ambulante de los vértices es el conjunto opaco de curva única más corto . ^[4] Sin embargo, para las barreras interiores de conjuntos convexos no poligonales que no son estrictamente convexos, o para barreras que no se requiere que estén conexas, 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 para la longitud de un conjunto opaco. ^{[3] [4]} ${\displaystyle K}$ ${\displaystyle \partial K}$ ${\displaystyle |\partial K|}$ ${\displaystyle K}$

Límite inferior

Existen varias pruebas de que un conjunto opaco para cualquier conjunto convexo debe tener una longitud total de al menos , la mitad del perímetro. Una de las más simples involucra 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 en líneas. Es conveniente simplificar el problema aproximando por un superconjunto estrictamente convexo, que puede elegirse para que tenga un perímetro arbitrariamente cercano al conjunto original. Entonces, a excepción de las líneas tangentes a (que forman una fracción evanescente de todas las líneas), una línea que interseca cruza su límite dos veces. Por lo tanto, si una línea aleatoria interseca con probabilidad , el número esperado de cruces de límite es . Pero cada línea que interseca interseca su conjunto opaco, por lo que el número esperado de intersecciones con el conjunto opaco es al menos , que es al menos la mitad que para . Por la fórmula de Crofton, las longitudes del límite y la barrera tienen la misma proporción que estos números esperados. ^[6] ${\displaystyle K}$ ${\displaystyle |\partial K|/2}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle p}$ ${\displaystyle 2p}$ ${\displaystyle K}$ ${\displaystyle p}$ ${\displaystyle K}$

Este límite inferior de sobre 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 se puede hacer 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 es el mejor posible. ^[6] Sin embargo, acercarse a de esta manera implica considerar una secuencia de formas en lugar de solo una forma única, porque para cualquier conjunto convexo que no sea un triángulo, existe un tal que todos los conjuntos opacos tienen una longitud de al menos . ^[7] ${\displaystyle |\partial K|/2}$ ${\displaystyle |\partial K|/2}$ ${\displaystyle |\partial K|/2}$ ${\displaystyle K}$ ${\displaystyle \delta }$ ${\displaystyle |\partial K|/2+\delta }$

Formas específicas

Para un triángulo , como para cualquier polígono convexo, el conjunto opaco conexo 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 (120°) o más, utiliza los dos bordes más cortos del triángulo, y de lo contrario consta de tres segmentos de línea desde los vértices hasta el punto de Fermat del triángulo. ^[9] Sin embargo, sin asumir la conectividad, no se ha demostrado la optimalidad del árbol de Steiner. Izumi ha demostrado una pequeña mejora en el límite inferior de reducción a la mitad del perímetro para el triángulo equilátero . ^[10] ${\displaystyle 2\pi /3}$

Problema sin resolver en matemáticas :

¿Cuáles son los conjuntos opacos más cortos para el cuadrado unitario y el círculo unitario?

(más problemas sin resolver en matemáticas)

Para un cuadrado unitario , el perímetro es 4, el perímetro menos el borde más largo es 3 y la longitud del árbol de Steiner mínimo es . Sin embargo, se conoce un bosque opaco desconectado más corto, con longitud . 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 de manera más general, pero esto sigue sin demostrarse. ^[7] El límite inferior de reducción a la mitad del perímetro de 2 para el cuadrado, ya probado por Jones, ^{[12] [13]} se puede mejorar ligeramente, a , para cualquier barrera que consista en como máximo un número contable de curvas rectificables , ^[7] mejorando límites anteriores similares que restringían que la barrera se colocara solo cerca del cuadrado dado. ^[6] ${\displaystyle 1+{\sqrt {3}}\approx 2.732}$ ${\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}$ ${\displaystyle 2.00002}$

Bosques opacos para un círculo unitario. Izquierda: barrera conectada óptima en forma de U, con longitud . Derecha: la mejor barrera conocida, con tres componentes y longitud . ${\displaystyle 2+\pi }$ ${\displaystyle \approx 4.7998}$

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 , ^[15] óptima 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 curva única a Menachem Magidor en 1974. ^[8] Para 1980, E. Makai ya había proporcionado una mejor solución de tres componentes, con una longitud de aproximadamente , ^[18] redescubierta por John Day en una continuación de la columna de Stewart. ^[19] La longitud desconocida de la solución óptima se ha llamado constante de detección de haz . ^[20] ${\displaystyle 2+\pi }$ ${\displaystyle 4.7998}$

Algoritmos

Dos algoritmos publicados afirman generar el bosque opaco óptimo para polígonos arbitrarios, basándose en la idea de que la solución óptima tiene una estructura especial: un árbol de Steiner para un triángulo en una triangulación del polígono , y un segmento en cada triángulo restante desde un vértice hasta el lado opuesto, de longitud igual a la altura del triángulo. Esta estructura coincide con la estructura conjeturada de la solución óptima para un cuadrado. Aunque la triangulación óptima para una solución de esta forma no es parte de la entrada a estos algoritmos, puede ser encontrada por los algoritmos en tiempo polinomial utilizando programación dinámica . ^{[21] [22]} Sin embargo, estos algoritmos no resuelven correctamente el problema para todos los polígonos, porque algunos polígonos tienen soluciones más cortas con una estructura diferente a las que encuentran. En particular, para un rectángulo largo y delgado, el árbol de Steiner mínimo de los cuatro vértices es más corto que la solución basada en triangulación que estos algoritmos encuentran. ^[23] Ningún algoritmo conocido ha garantizado encontrar una solución correcta al problema, independientemente de su tiempo de ejecución. ^[3]

A pesar de este inconveniente, la barrera de curva única más corta de un polígono convexo, que es la ruta del vendedor ambulante de sus vértices, se puede calcular exactamente en tiempo polinomial para polígonos convexos mediante un algoritmo de programación dinámica , en modelos de cálculo para los que se pueden calcular exactamente las sumas de radicales . ^[4] También ha habido estudios más exitosos de algoritmos de aproximación para el problema y para determinar la cobertura de una barrera dada.

Aproximación

Según los límites generales para la longitud del bosque opaco 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 razones de aproximación que dos:

• Para conjuntos opacos generales, proporcionan un algoritmo cuya relación de aproximación es como máximo 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 estirada 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 cuadro. ^[4] $${\displaystyle {\frac {1}{2}}+{\frac {2+{\sqrt {2}}}{\pi }}\approx 1.5868.}$$
• Para los conjuntos opacos que consisten en un solo arco, proporcionan un algoritmo cuya razón de aproximación es como máximo La barrera resultante está definida por 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 puntos finales de este intervalo mediante una curva en forma de U estirada 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 que se minimiza la longitud de la barrera resultante. ^[4] $${\displaystyle {\frac {\pi +5}{\pi +2}}\approx 1.5835.}$$
• Para los conjuntos opacos conectados, proporcionan un algoritmo cuya razón de aproximación es como máximo . Este método combina la barrera de un solo arco 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] ${\displaystyle 1.5716}$
• Para las barreras interiores, proporcionan un algoritmo cuya relación de aproximación es como máximo . ^[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] ${\displaystyle 1.7168}$

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

Cobertura

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

• Encuentra la envoltura convexa de cada componente conectado del bosque.
• Para cada vértice del casco, trazar una línea circularmente alrededor de , 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 p}$ ${\displaystyle p}$ ${\displaystyle C_{p}}$
• Encuentra la intersección de todos los conjuntos . Esta intersección es la cobertura del bosque. ${\displaystyle C_{p}}$

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

Aunque es ó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 se puede mejorar heurísticamente en la práctica mediante una fase de preprocesamiento que fusiona pares superpuestos de envolturas hasta que todas las envolturas restantes estén disjuntas, en el tiempo . Si esto reduce la entrada a una sola envoltura, no es necesario ejecutar el algoritmo de barrido e intersección más costoso: en este caso, la envoltura es la región de cobertura. ^[26] ${\displaystyle O(n\log ^{2}n)}$

Conjuntos opacos sin curvas

Las primeras cuatro etapas de una construcción de Bagemihl para conjuntos fractales opacos para el cuadrado unitario

Mazurkiewicz (1916) demostró que es posible que un conjunto opaco evite contener curvas no triviales y aún así tenga una longitud total finita. ^[1] Una construcción simplificada de Bagemihl (1959), que se muestra en la figura, produce un ejemplo para el cuadrado unitario. La construcción comienza con segmentos de línea que forman un conjunto opaco con una propiedad adicional: los segmentos de pendiente negativa bloquean todas las líneas de pendiente no negativa, mientras que los segmentos de pendiente positiva bloquean todas las líneas de pendiente no positiva. En la figura, los segmentos iniciales con esta propiedad son cuatro segmentos disjuntos a lo largo de las diagonales del cuadrado. Luego, subdivide repetidamente estos segmentos mientras mantiene esta propiedad. En cada nivel de la construcción, cada segmento de línea se divide por un pequeño espacio cerca de su punto medio en dos segmentos de línea, con pendiente del mismo signo, que juntos bloquean todas las líneas de signo opuesto que estaban bloqueadas por el segmento de línea original. El conjunto límite de esta construcción es un espacio de Cantor que, como todas las etapas intermedias de la construcción, es un conjunto opaco para el cuadrado. Con tamaños de brecha que disminuyen rápidamente, la construcción produce un conjunto cuya dimensión de Hausdorff es uno, y cuya medida de Hausdorff unidimensional (una noción de longitud adecuada para tales conjuntos) es finita. ^[2]

Los conjuntos de distancias del límite de un cuadrado, o del conjunto opaco conocido más corto de cuatro segmentos para el cuadrado, contienen todas las distancias en el intervalo de 0 a . Sin embargo, utilizando construcciones fractales similares, también es posible encontrar conjuntos fractales opacos cuyos conjuntos de distancias omiten infinitas distancias en este intervalo, o que (asumiendo la hipótesis del continuo ) forman un conjunto de medida cero . ^[2] ${\displaystyle {\sqrt {2}}}$

Historia

Los conjuntos opacos fueron estudiados originalmente por Stefan Mazurkiewicz en 1916. ^[1] Otros trabajos tempranos sobre conjuntos opacos incluyen los artículos de HM Sen Gupta y NC Basu Mazumdar en 1955, ^[27] y de Frederick Bagemihl en 1959, ^[2] pero estos tratan principalmente sobre los conjuntos de distancias y las propiedades topológicas de las barreras en lugar de sobre la minimización de su longitud. En una posdata a su artículo, Bagemihl pidió la longitud mínima de una barrera interior para el cuadrado, ^[2] y el trabajo posterior se ha centrado en gran medida en versiones del problema que implican la minimización de la longitud. Se han planteado repetidamente, con múltiples formulaciones coloridas: cavar una zanja de la longitud más corta posible para encontrar un cable telefónico enterrado recto, ^[8] tratar de encontrar un camino recto cercano mientras se está perdido en un bosque, ^[17] nadar hasta una costa recta mientras se está perdido en el mar, ^[4] pintar paredes de manera eficiente para hacer opaca una casa de vidrio, ^[28] etc.

El problema también se ha generalizado a conjuntos que bloquean todas las geodésicas en una variedad de Riemann , ^{[29] [30]} o que bloquean líneas a través de conjuntos en dimensiones superiores. En tres dimensiones, la pregunta correspondiente pide una colección de superficies de área total mínima que bloquee toda visibilidad a través de un sólido. Sin embargo, para algunos sólidos, como una pelota, no está claro si existe tal colección o si, en cambio, el área tiene un ínfimo que no se puede alcanzar. ^{[8] [31]}

Véase también

• El problema de Bellman: "Perdido en el bosque"
• El huerto de Euclides

Referencias

1. Mazurkiewicz, Stefan (1916), "Sur un ensemble fermé, punctiforme, qui rencontre toute droite passant par un sure domaine", Prace Mat.-Fiz. (en polaco y francés), 27 : 11-16
2. Bagemihl, F. (1959), "Algunos subconjuntos opacos de un cuadrado", Michigan Mathematical Journal , 6 (2): 99–103, doi :10.1307/mmj/1028998183, MR  0105657
3. Provan, J. Scott; Brasil, Marco; Thomas, Doreen ; Weng, Jia F. (2012), Cubiertas opacas mínimas para regiones poligonales , arXiv : 1210.8139 , Bibcode :2012arXiv1210.8139P
4. Dumitrescu, Adrián; Jiang, Minghui; Pach, János (2014), "Conjuntos opacos", Algorithmica , 69 (2): 315–334, arXiv : 1005.2218 , doi : 10.1007/s00453-012-9735-2, MR  3183418, S2CID  13884553
5. Kawohl, Bernd (1997), "El cuadrado opaco y el círculo opaco", en Bandle, Catherine ; Everitt, William N.; Losonczi, Laszlo; Walter, Wolfgang (eds.), Desigualdades generales, 7 (Oberwolfach, 1995) , International Series of Numerical Mathematics, vol. 123, Basilea: Birkhäuser , págs. 339–346, doi :10.1007/978-3-0348-8942-1_27, ISBN 978-3-0348-9837-9, Sr.  1457290
6. Dumitrescu, Adrian; Jiang, Minghui (2014), "El cuadrado opaco", Proc. 30.º Simposio Anual sobre Geometría Computacional (SoCG'14) , Nueva York: Association for Computing Machinery, págs. 529–538, arXiv : 1311.3323 , doi : 10.1145/2582112.2582113, ISBN 978-1-4503-2594-3, MR  3382335, S2CID  207211457
7. Kawamura, Akitoshi; Moriyama, Sonoko; Otachi, Yota; Pach, János (2019), "Un límite inferior en conjuntos opacos" (PDF) , Geometría computacional , 80 : 13–22, doi :10.1016/j.comgeo.2019.01.002, MR  3945133
8. Faber, V. ; Mycielski, J. (1986), "La curva más corta que se encuentra con todas las líneas que se encuentran con un cuerpo convexo", The American Mathematical Monthly , 93 (10): 796–801, doi :10.2307/2322935, JSTOR  2322935, MR  0867106
9. Nahin, Paul J. (2021), "Capítulo 7: Comienza la era moderna", When Least Is Best: How Mathematicians Discovered Many Clever Ways to Make Things as Small (or as Large) as Possible (Cuando lo mínimo es lo mejor: cómo los matemáticos descubrieron muchas formas ingeniosas de hacer las cosas lo más pequeñas (o lo más grandes) posible) , Princeton University Press , págs. 279–330, doi :10.2307/j.ctv19qmf43.12, JSTOR  j.ctv19qmf43.12
10. Izumi, Taisuke (2016), "Mejora del límite inferior de los conjuntos opacos para el triángulo equilátero", Discrete Applied Mathematics , 213 : 130–138, doi : 10.1016/j.dam.2016.05.006 , MR  3544574
11. Honsberger, Ross (1978), "Problema 12: Un cuadrado opaco", Mathematical Morsels , The Dolciani Mathematical Expositions, vol. 3, Nueva York: Mathematical Association of America , págs. 22-25, ISBN 978-0-88385-303-0, Sr.  0490615
12. Jones, Robert Edward Douglas (1962), "Capítulo 4: Subconjuntos opacos de un cuadrado", Medida lineal y conjuntos opacos, Tesis y disertaciones retrospectivas, vol. 2058, Iowa State University , págs. 36–45, doi :10.31274/rtd-180813-2223
13. Jones, RED (1964), "Conjuntos opacos de grado ", The American Mathematical Monthly , 71 : 535–537, doi :10.2307/2312596, JSTOR  2312596, MR  0164898 ${\displaystyle \alpha }$
14. Kawohl, Bernd (2000), "Algunos problemas de optimización de formas no convexas", Optimal shape design (Tróia, 1998) , Lecture Notes in Mathematics, vol. 1740, Berlín: Springer , pp. 7–46, doi :10.1007/BFb0106741, ISBN 978-3-540-67971-4, Sr.  1804684
15. Stewart, Ian (septiembre de 1995), "El gran robo de desagües", Scientific American , 273 (3): 206–207, Bibcode :1995SciAm.273c.206S, doi :10.1038/scientificamerican0995-206, JSTOR  24981805
16. Eggleston, HG (1982), "El radio interno máximo de la cubierta convexa de un conjunto plano conexo de longitud dada", Actas de la London Mathematical Society , Tercera serie, 45 (3): 456–478, doi :10.1112/plms/s3-45.3.456, MR  0675417
17. Joris, H. (1980), "Le chasseur perdu dans la forêt", Elemente der Mathematik (en francés), 35 (1): 1–14, SEÑOR  0559167; traducido al inglés por Steven Finch, arXiv :1910.00615
18. Makai, E. Jr. (1980), "Sobre un problema dual de Tarski's Plank", 2.º Coloquio sobre geometría discreta , Inst. Math. Univ. Salzburg, págs. 127-132, Zbl  459.52005
19. Stewart, Ian (febrero de 1996), "Feedback", Scientific American , 274 (2): 125, JSTOR  24989406
20. Finch, Steven R. (2003), "8.11 Constante de detección de haz", Constantes matemáticas , Enciclopedia de matemáticas y sus aplicaciones, Cambridge University Press , págs. 515–519, ISBN 978-0-521-81805-6
21. Akman, Varol (1987), "Un algoritmo para determinar un bosque mínimo opaco de un polígono convexo", Information Processing Letters , 24 (3): 193–198, doi :10.1016/0020-0190(87)90185-2, MR  0882227, S2CID  37582183
22. Dublish, Pratul (1988), "Un algoritmo para encontrar el bosque opaco mínimo de un polígono convexo", Information Processing Letters , 29 (5): 275–276, doi :10.1016/0020-0190(88)90122-6, MR  0981078 ${\displaystyle O(n^{3})}$
23. Shermer, Thomas (1991), "Un contraejemplo de los algoritmos para determinar bosques mínimos opacos", Information Processing Letters , 40 (1): 41–42, doi :10.1016/S0020-0190(05)80008-0, MR  1134007
24. Dumitrescu, Adrián; Jiang, Minghui; Tóth, Csaba D. (2015), "Computación de barreras interiores opacas a la Shermer", Revista SIAM de Matemáticas Discretas , 29 (3): 1372–1386, doi :10.1137/14098805X, hdl : 10211.3/198469 , SEÑOR  3376125
25. Beingessner, Alexis; Smid, Michiel (2012), "Computing the coverage of an opaco forest" (PDF) , Actas de la 24.ª Conferencia Canadiense sobre Geometría Computacional (CCCG'12) , págs. 95-100
26. Barba, Luis; Beingessner, Alexis; Bose, Prosenjit ; Smid, Michiel (2013), "Cálculo de la cobertura de los bosques de plátanos" (PDF) , Proc. 25.ª Conferencia Canadiense sobre Geometría Computacional (CCCG'13)
27. Sen Gupta, HM ; Basu Mazumdar, NC (1955), "Una nota sobre ciertos conjuntos de puntos planos", Boletín de la Sociedad Matemática de Calcuta , 47 : 199–201, MR  0080287
28. Smart, JR (abril de 1966), "En busca de talento matemático en Wisconsin, II", The American Mathematical Monthly , 73 (4): 401–409, doi :10.2307/2315418, JSTOR  2315418; ver Problema 4, Problema 5, pág. 405
29. Croft, HT (1969), "Curvas que intersecan ciertos conjuntos de círculos máximos en la esfera", Journal of the London Mathematical Society , Segunda serie, 1 : 461–469, doi :10.1112/jlms/s2-1.1.461, MR  0247601
30. Asimov, Daniel; Gerver, Joseph L. (2008), "Múltiples opacas mínimas", Geometriae Dedicata , 133 : 67–82, doi :10.1007/s10711-008-9234-4, SEÑOR  2390069, S2CID  122556952
31. Brakke, Kenneth A. (1992), "El problema del cubo opaco", The American Mathematical Monthly , 99 (9): 866–871, doi :10.2307/2324127, JSTOR  2324127, MR  1191707