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

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

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

Если кто найдет простой способ убить эту задачу, я бы с удовольствием посмотрел.