Здравствуйте George_Seryakov, Вы писали:

GS>Здравствуйте Sinclair, Вы писали:

S>>Ессно, мы тут программеры, так что надо написать программу, которая оптимально размещает окружности и строит диаметр. Уверен, что можно выполнить ее за время N*log(N). В хорошем случае за N.

GS>Боюсь, что дело куда сложнее. Можно упростить задачу, рассматривая ее как нахождение минимальной описывающей окружности для данного количества (N) непересекающихся окружностей меньшего радиуса. Тогда мы имеем классическую задачу на оптимизацию в 2N пространстве с N*(N-1)/2 связями. Минимизируемая фугкция неаналитическая. Найти нужно все локальные минимумы. Минимумы будут находиться у ограничений. Похоже, сама оценка вычислительной сложности нетривиальна. В любом случае — существенно многомерные задачи оптимизации имеют экспоненциальную сложность по числу степеней свободы.

GS>Если кто найдет простой способ убить эту задачу, я бы с удовольствием посмотрел.
Окружность, внутри которой находятся диски:
X, Y, R – параметры, задающие описанную окружность.
Xi, Yi, Ri – параметры, задающие отдельный диск, i = 1..N.
Требуется найти

min R

по X, Y и всем Xi, Yi, таким, что
{диски должны не пересекаться}
1. sqr(Xi-Xj)+sqr(Yi-Yj) >= sqr(Ri+Rj) для всех i<>j, i, j = 1..N
{диски должны находиться внутри описанной окружности}
2. sqr(Xi-X) + sqr(Yi-Y)<= sqr(R) — sqr(Ri), i = 1..N.

Получена задача минимизации с ограничениями типа неравенств. Можно построить точную строго выпуклую штрафную функцию (с использованием функции Лагранжа) для этой задачи, которая в окрестности одного из возможных решений будет строго выпуклой (скорее всего при одинаковом радиусе вписываемых дисков решение будет единственным). Численная минимизация ее (лучше всего с помощью метода Ньютона – достаточно всего 7-10 итераций) и даст «наиболее близкое» к исходному приближению решение.