Círculo de embalaje - ¿Cómo obtener la longitud mínima?

Question

En un pasado de admisión de papel de una universidad local, me encontré con un problema que no podía resolver.

Dado $n$ círculos con sus respectivos radios $r_1, r_2, \dotsc , r_n,$ estamos para encontrar el mínimo ancho de un rectángulo para encapsular todos los dados de los círculos. La colocación de los círculos, junto con un caso de ejemplo puede ser encontrado aquí:

El problema, como yo lo veo, es la identificación de la superposición de parte de los segmentos determinados por los radios de los círculos adyacentes de diferentes diámetros, y deducir la longitud de cualquier segmento de la superposición de del total de la suma de los radios.

Puede ser porque no tengo formación en geometría, o simplemente estoy perdiendo algo trivial, pero no puedo ver una solución. ¿Cómo se podría solucionar esto?

Answer 1

Estoy asumiendo que los círculos tienen que ser colocadas como se ilustra tangente a la arista común en el orden en que se especifican, es decir, no estamos barajando los círculos alrededor de resolver un arbitrario de embalaje.

Todavía habrá algo complicado de los casos, cuando adyacentes círculos son significativamente diferentes diámetros. Sin embargo, en el caso de que el círculo tamaños son suficientemente similares que cada círculo toca sólo sus dos vecinos inmediatos (y el final de los círculos en contacto con los lados del rectángulo), la distancia entre adyacente círculo de los centros es simplemente la proyección de la distancia de la línea entre los dos centros: $$d_i = \sqrt{(r_i + r_{i+1})^2 - (r_i - r_{i+1})^2 } $$ donde $d_i \;(i=[1..n-1])$ es la distancia incremento de centro a centro.

El ancho total es, a continuación, $$r_1+\sum_1^{n-1}{d_i}+r_n$$

Para el ilustrado caso, que la $$2+2\sqrt{(9-1)}+2 = 4+2\sqrt {\bbox[1px]{8}} \approx 9.657$$