Cubra por completo un rectángulo con una cantidad mínima de círculos de radio fijo

Question

He tenido este problema durante algunos años. Fue en un concurso de informática en mi ciudad hace un tiempo. No pude resolverlo, y mi maestro no pudo resolverlo. No he conocido a nadie que haya podido resolverlo. Nadie que yo conozca sabe la manera correcta de dar la respuesta, por lo que decidí publicar aquí: problema

Ze

Dado un rectángulo, X por Y, encontrar la cantidad mínima de círculos N con una fija dado el radio R, necesario para cubrir completamente cada parte del rectángulo.

---

He pensado en maneras de resolverlo, pero no tengo nada definitivo. Si cada círculo define un rectángulo interno, entonces R^2 = Wi^2 + Hi^2, donde Wi y Hi son el ancho y la altura del área práctica cubierta por cada círculo i. Al principio pensé que debería hacer Wi igual a Wj para cualquier i = j, lo mismo para H. De esta forma, podría simplificar el problema haciendo que las relaciones ancho/alto sean iguales al rectángulo principal (Wi/Hi = X/Y). De esa manera, N=X/Wi. Pero esa solución seguramente es incorrecta en el caso de que X exceda en gran medida Y o viceversa.
La segunda idea fue que Wi = Hi para cualquier i dado. De esta forma, los cuadrados llenan el espacio de manera más eficiente. Sin embargo, si queda una tira muy angosta, es mucho más óptimo usar rectángulos para rellenarla, o mejor aún, usar rectángulos para la última fila antes de eso también.
Luego me di cuenta de que ninguna de las ideas es la óptima, ya que siempre puedo encontrar mejores formas de hacerlo. Siempre será cercano al final, pero no final.

Editar
En algunos casos (rectángulo grande) que une hexágonos parece ser una solución mejor que las plazas de unión.

Además Editar
Aquí hay una comparación de 2 métodos: trébol vs hexagonal. Hexagonal es, obviamente, mejor, para superficies grandes. Sin embargo, creo que cuando el rectángulo es lo suficientemente pequeño, el método rectangular puede ser más eficiente. Es una corazonada. Ahora, en la imagen, verá 14 círculos a la izquierda y 13 círculos a la derecha. Aunque la superficie difiere mucho más (doble) que un círculo. Es porque a la izquierda se superponen menos, por lo tanto, desperdician menos superficie.

Las preguntas siguen siendo:

1. Es el propio patrón de hexágono regular óptima? O ciertos ajustes deben hacerse en partes del rectángulo principal.
2. ¿Hay razones para no usar formas regulares como "solución definitiva"?
3. ¿Esta pregunta tiene una respuesta? :)

Answer 1

Cuando los círculos se disponen como un trébol con cuatro hojas con un quinto círculo en el medio, un círculo cubrirá un área igual a R * 2 * R. En esta disposición, la pregunta es: ¿cuántos círculos que cubren un área de R * 2 * R cubrirán un área de W * H?, o N * R * 2 * R = W * H. Entonces N = W * H/R * 2 * R.

Answer 2

Para X e Y grande en comparación con R, un patrón hexagonal (en forma de panal) es casi óptimo. La distancia entre los centros de los círculos en la dirección X es sqrt(3)*R. La distancia entre las filas en la dirección Y es 3*R/2, por lo que necesita aproximadamente X*Y/R^2 * 2*/(3*sqrt(3)) círculos.

Si utiliza un modelo cuadrado, la distancia horizontal es mayor (2*R), pero la distancia vertical es mucho menor (R), por lo que necesitaría unos X*Y/R^2 * 1/2 círculos. Desde 2/(3*sqrt(3) < 1/2, el patrón hexagonal es la mejor oferta.

Tenga en cuenta que esto es solo una aproximación. Por lo general, es posible agitar un poco el patrón regular para hacer que algo encaje donde el patrón estándar no lo haría. Esto es especialmente cierto si X e Y son pequeñas en comparación con R.

En términos de sus preguntas específicas:

1. El patrón hexagonal es un recubrimiento óptimo de todo el plano. Con X e Y finitos, creo que a menudo es posible obtener un mejor resultado. El ejemplo trivial es cuando la altura es menor que el radio. En ese caso, puede mover los círculos en la fila más alejada hasta que la distancia entre los puntos de intersección de cada par de círculos sea igual a Y.

2. Tener un patrón regular impone restricciones adicionales a la solución, por lo que la solución óptima bajo esas restricciones puede no ser óptimo con esas restricciones eliminadas. En general, los patrones algo irregulares pueden ser mejores (ver la página vinculada por mbeckish).

3. Los ejemplos en esa misma página son todas soluciones específicas. Las soluciones con más círculos se parecen un poco al patrón hexagonal. Aún así, no parece haber una solución cerrada.

Answer 3

This sitio ataca el problema desde un ángulo ligeramente diferente: Teniendo en cuenta los círculos de unidad n, ¿cuál es la plaza más grande que puede cubrir?

Como puede ver, a medida que cambia el número de círculos, también lo hace el patrón de cobertura.

Para su problema, creo que esto implica: diferentes dimensiones rectangulares y tamaños de círculos dictarán diferentes patrones de cobertura óptimos.

Answer 4

El hexágono es mejor que el diamante. Considere el porcentaje de área de la unidad de círculo cubierto por cada uno:

#!/usr/bin/env ruby 

include Math 

def diamond 
    # The distance from the center to a corner is the radius. 
    # On a unit circle, that is 1. 
    radius = 1 

    # The edge of the nested diamond is the hypotenuse of a 
    # right triangle whose legs are both radii. 
    edge = sqrt(radius ** 2 + radius ** 2) 

    # The area of the diamond is the square of the edge 
    edge ** 2 
end 

def hexagon 
    # The hexagon is composed of 6 equilateral triangles. 
    # Since the inner edges go from the center to a hexagon 
    # corner, their length is the radius (1). 
    radius = 1 

    # The base and height of an equilateral triangle whose 
    # edge is 'radius'. 
    base = radius 
    height = sin(PI/3) * radius 

    # The area of said triangle 
    triangle_area = 0.5 * base * height 

    # The area of the hexagon is 6 such triangles 
    triangle_area * 6 
end 

def circle 
    radius = 1 
    PI * radius ** 2 
end 

puts "diamond == #{sprintf "%2.2f", (100 * diamond/circle)}%" 
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon/circle)}%" 

Y

$ ./geometrons.rb 
diamond == 63.66% 
hexagon == 82.70% 

Además, hexágonos regulares son de más alto vértice del polígono que forman un regular tessellation of the plane.

Answer 5

Según mis cálculos, la respuesta correcta es:

D=2*R; X >= 2*D, Y >= 2*D, 
N = ceil(X/D) + ceil(Y/D) + 2*ceil(X/D)*ceil(Y/D) 

En el caso particular si el resto de X/D y L/D igual a 0, entonces

N = (X + Y + X*Y/R)/D 

Case 1: R = 1, X = 2, Y = 2, then N = 4 

Case 2: R = 1, X = 4, Y = 6, then N = 17 

Case 3: R = 1, X = 5, Y = 7, then N = 31 

Espero que ayuda.