Две задачи с кругами, которые под силу только гению

[reqyz]

1. Дан набор произвольного количество кругов произвольного радиуса. Необходимо найти минимальный круг, по периметру которого можно расположить центры данных кругов, так, чтобы круги не пересекались.
2. Дан набор произвольного количества кругов произвольного радиуса. Необходимо найти минимальный круг, по периметру которого можно расположить данные круги, так, чтобы они не пересекались.



У меня нет решения данных задач, поэтому я поделюсь тем, как я пытался их решить, и буду надеяться, что на этом форуме есть гений, способный завершить решения.



1. Основной круг можно разделить на множество парных равнобедренных треугольников, основания которых будут равны радиусам данных кругов, а стороны будут равны искомому радиусу. При этом сумма углов противолежащих основанию всех равнобедренных треугольников равна 360.

Преобразовываем формулу равнобедренного треугольника: \cos{2\times\alpha_{n}} = -\frac{R_{n}}{2\times R}; \sum\alpha_{n} = 180^{\circ}; R=?
Объединяем формулы: \sum\arccos{-\frac{R_{n}}{2\times R}}=360^{\circ}

Вывести из этой формулы R мне не удалось. Возможно я иду не тем путем, в чем то ошибся или не вижу очевидных следующих шагов. А вы?

2. Основной круг можно разделить на множество треугольников, сторонами которых будут суммы их радиусовоснования которых будут равны радиусам данных кругов, а стороны будут равны искомому радиусу. При этом сумма углов противолежащих основанию всех равнобедренных треугольников равна 360.

Используем формулу нахождения угла по трем сторонам треугольника: \cos{\alpha_{n}} = \frac{(R+R_{n} )^{2}+(R+R_{n+1})^{2}-(R_{n}+R_{n+1})}{2\times(R+R_{n})\times(R+R_{n+1})}; \sum\alpha_{n} = 360^{\circ};
Объединяем формулы: \sum\arccos{\frac{(R+R_{n} )^{2}+(R+R_{n+1})^{2}-(R_{n}+R_{n+1})}{2\times(R+R_{n})\times(R+R_{n+1})}}=360^{\circ}
Для последнего n, n+1 = 0

Вывести из этой формулы R мне так же не удалось. Возможно получится у вас.

[svv]

А оно же ещё и от порядка зависит.
Одни и те же восемь серых кругов слева умещаются вокруг жёлтого, а справа нет. То есть существуют экономные и неэкономные конфигурации.

[tolstopuz]

Первая картинка неправильная - три окружности не пересекаются в одной точке.

В любом случае решать надо численно. Если порядок кругов задан, то это просто численное нахождение корня уравнения, а если их можно менять местами, то все гораздо сложнее.

[svv]

Ещё один источник сложностей. Перенумеруем круги от $1$ до $n$. При некоторых значениях радиусов невозможно соблюсти требование:
Друг друга касаются те и только те круги, которые являются соседними в списке: $1,2,...,n,1$.
Хотя этого требования нет в условиях задачи, Вы выводили формулы исходя из него (считая его естественным).

Но вот пример, когда требование нарушается (и потому формулы становятся неверными), а условия задачи — нет. Зелёный кружок не может одновременно касаться предыдущего и последующего соседа, зато они друг друга касаются.

[reqyz]

svv
Спасибо за конструктивные комментарии.
По умолчанию предполагается располагать круги в том порядке, в котором они даны. Но вариант с любым другим расположением тоже рассматривается, если для него существует какое-либо решение.

Действительно в моих рассуждениях решения второй задачи не учтено возможное пересечение не соседних кругов. Значит вероятно для не я иду неверным путем. Буду думать как учесть такое пересечения.

[B@R5uk]

reqyz в сообщении #1603491 писал(а):

По умолчанию предполагается располагать круги в том порядке, в котором они даны.

Похоже на вариант задачи по программированию.

[r-aax]

Предложу следующий подход к решению задачи 2.

I. Рассмотрим небольшую вспомогательную задачку.

Дана окружность $(O_r, r)$. Ее касаются две окружности $(O_a, a)$ и $(O_b, b)$ (в точках $A$ и $B$ соответственно). Сами окружности $(O_a, a)$ и $(O_b, b)$ между собой также касаются (в точке $M$).
Требуется найти следующие величины:
$C(a, b, r)$ - длина отрезка $AB$, то есть расстояние между точками касания,
$L(a, b, r)$ - длина дуги $AB окружности $(O_r, r)$.

Сначала найдем $C(a, b)$. По теореме косинусов из треугольника $O_rO_aO_b$ найдем $\alpha = \angle O_aO_rO_b$, подставим в теорему косинусов для треугольника $O_rAB$ и выразим $AB$. Получим

$C(a, b, r) = AB = \frac{2}{\sqrt{\frac{1}{a b} + \frac{1}{a r} + \frac{1}{b r} + \frac{1}{r^2}}}$

Зная хорду, нетрудно найти и дугу:

$L(a, b, r) = 2 r \arcsin{\frac{C(a, b, r)}{2 r}}$

II. Пусть теперь у нас есть все та же окружность $(O_r, r)$, но ее касается набор других окружностей с радиусами $r_i$, $0 \le i \le n - 1$, и все эти окружности последовательно касаются друг друга (как в условии задачи, то есть нулевая касается первой, первая касается второй, ..., последняя касается нулевой).

Если вся эта конструкция собралась правильно, и последняя окружность смогла коснуться нулевой, будет выполняться условие

$S(r_i, i \le 0 \le n - 1, r) = \sum_{i = 0}^{n - 1}{L(r_i, r_{(i + 1)\mod n}, r)} = 2 \pi r$

то есть, посчитав все попарные дуги между точками касания на окружности $(O_r, r)$, мы получим всю длину этой окружности.

Если мы выберем радиус $r$ слишком маленьким, то выражение $S(r_i, i \le 0 \le n - 1, r)$ окажется больше длины окружности $2 \pi r$. Если мы выберем радиус r слишком большим, то выражение $S(r_i, i \le 0 \le n - 1, r)$ будет наоборот меньше длины окружности $2 \pi r$. Таким образом, искомый радиус - корень следующего уравнения:

$\sum_{i = 0}^{n - 1}{L(r_i, r_{(i + 1)\mod n}, r)} - 2 \pi r = 0$

Аналитически решить такое уравнение не берусь, но численно оно решается без проблем.

III. Определение порядка касания окружностей.

Как уже было отмечено в теме, значение искомого радиуса существенно зависит от порядка, в котором расположены окружности с радиусами $r_i$. На тему определения порядка требуется некое строгое обоснование, однако полный перебор всех вариантов расположения окружностей показывает, что оптимальным вариантом является жадное расположение, при котором мы сначала пытаемся расположить рядом окружности с наибольшей разницей в радиусах.

Например:
Пусть даны радиусы $[1, 2, 4, 6, 8, 15]$. Наибольшая разница в радиусах это $15 - 1 = 14$, расположим и рядом. Следующая максимальная разница, которую мы можем получить это $15 - 2 = 13$, располагаем $2$ с другой стороны от $15$ (на этом этапе число $15$ выбывает, так как окружено с двух сторон). Следующая максимальная разница это $8 - 1 = 7$, располагаем $8$ рядом с $1$. И так далее, получим следующую оптимальную перестановку:
$[1, 2, 4, 6, 8, 15] \rightarrow [1, 8, 4, 6, 2, 15]$.

P.S. На диких конфигурациях это может не работать. Например, если мы расположим последовательно окружности с радиусами $[10^6, 1, 10^6]$, то конечно у крайних двух двух между собой будет конфликт.

[svv]

r-aax в сообщении #1603529 писал(а):

$\alpha = \angle O_aO_rO_b$

Теперь дугу можно найти и так: $L(a,b,r)=r\alpha$. Правильно?
А вообще, вместо условия «сумма длин всех дуг равна $2\pi r$» можно использовать условие «сумма всех углов равна $2\pi$». Углы Вы уже нашли по теореме косинусов, так что $C$ и $L$ вычислять не нужно.

[r-aax]

svv в сообщении #1603536 писал(а):

r-aax в сообщении #1603529 писал(а):

$\alpha = \angle O_aO_rO_b$

Теперь дугу можно найти и так: $L(a,b,r)=r\alpha$. Правильно?

Конечно можно и так, углы - те же дуги.
Честно говоря, я сначала вычислил хорду $C(a, b, r)$, и формула для нее мне показалась настолько красивой (да еще и работающей для бесконечного радиуса $r$), что я решил ее оставить.

[reqyz]

r-aax. Потрясающее решение.

[r-aax]

В задаче 1 меняется только выражение для хорды, она по построению просто равна сумме радиусов $C(a, b) = a + b$. Все остальное - без изменений.