Número mínimo de puntos para intersecar cualquier círculo en la región

Question

Arreglar algunos $r$ , $x$ y $y$ .

Suponga que tiene una región rectangular que mide $x \times y$ . Puede colocar un círculo de radio $r$ en cualquier lugar de la región.

Se desea colocar los puntos en la región de manera que, independientemente de dónde se coloque el círculo dentro de la región, el círculo intersecte al menos uno de los puntos de la región.

La pregunta es: ¿cuál es el número mínimo de puntos, según $r,x,y$ ? Está claro que algunas disposiciones de puntos son más eficaces que otras. (Por si sirve de algo: Estoy tratando de encontrar el arreglo más eficiente - la expresión real de forma cerrada para el número mínimo de puntos es de importancia secundaria).

No estoy seguro de si esto es útil, pero los puntos situados en la frontera de la región no cuentan. Puedes suponer que si el círculo interseca la frontera, eso cuenta como si intersectara un punto.

---

Hasta ahora, la mejor disposición de los puntos que he encontrado ha sido una cuadrícula en la que espaciamos los puntos con una distancia de $r\sqrt{2}$ . La idea es que este espaciamiento produce una distancia de $2r$ (es decir, el diámetro del círculo) entre los puntos que son diagonales entre sí.

Creo que esta es la disposición óptima para una cuadrícula, pero tengo curiosidad por saber si hay mejores disposiciones no cuadriculadas. Creo que esto está intuitivamente relacionado con los problemas de cobertura (agradecería ayuda para desarrollar esta línea de pensamiento), y sé que para el empaquetamiento de círculos, un mosaico hexagonal es óptimo. Me pregunto si hay una solución similar aquí.

Answer 1

Quieres que cada punto de tu rectángulo tenga una distancia de como máximo $r$ a al menos uno de los puntos de su conjunto. Lo que significa que todo el rectángulo debe ser cubierto mediante círculos de radio $r$ centrado en sus puntos, lo que hace que este problema de cobertura . Los problemas de cobertura suelen ser duales a los de embalaje, por lo que su comparación con el embalaje en círculo ya iba en la dirección correcta.

Debe haber una amplia literatura al respecto. Por ejemplo, Cubrir un rectángulo con círculos iguales y Cubrir un rectángulo con seis y siete círculos aparentemente se discuten casos de hasta 7 círculos, centrándose en la optimización. Cubrir un conjunto poligonal compacto con círculos idénticos busca los óptimos locales en una configuración más general. Artículos generales como Empaquetamiento, recubrimiento y mosaico en espacios bidimensionales puede proporcionar indicaciones útiles. No he leído nada de esto, sólo he buscado en Google Scholar. El mensaje es que estos problemas son realmente difíciles de resolver con garantía de optimalidad, pero son objeto de investigación.

Esta página tiene un listado ilustrado de formas de cubrir cuadrados con un número determinado de círculos de radio mínimo, utilizando hasta 12 círculos. Puede darte una idea de las configuraciones que puedes esperar. La mayoría de ellas no siguen una cuadrícula regular, aunque las irregularidades son más pronunciadas para algunos números de círculos que para otros. Si esperas un gran número de círculos y quieres optar por una cuadrícula regular, debes elegir una cuadrícula hexagonal, ya que tiene menos solapamiento entre círculos adyacentes. Cuando se cubre todo el plano, esto es óptimo, y por lo tanto, para los rectángulos que son grandes en comparación con el radio, esto debería seguir siendo cerca de lo óptimo.