Оптимальная расстановка

[ZheniaM]

Уважаемые коллеги! Нужна помощь в следующем вопросе:

Имеются $M$ шаров с одинаковыми радиусами $R$, которые располагаются неким образом в замкнутой фигуре (для определённости можно положить, что это прямоугольник, хотя в более общем фигура образованная пересечением плоскостей).
Пусть $(x_1,y_1), (x_2,y_2),\ldots, (x_M, y_M)$ координаты центров окружностей. Обозначим площадь пересечения неких двух окружностей как $S^1_{i,j}$. Если пересекаются три окружности между собой, то обозначим площадь пересечения таких окружностей как $S^2_{i,j,k}$. Требуется так расставить исходные окружности, чтобы максимизировать суммарную площадь пересечения двух и трёх окружностей (с разными весовыми коэффициентами). Тоесть

$$\alpha_1\sum_{i,j}S^1_{i,j}+\alpha_2\sum_{i,j,k}S^2_{i,j,k}\to\max,$$

где весовые коэффициенты заданы (можно для определённости положить, что $\alpha_1=0.3, \alpha_2=0.6$. Тоесть большому пересечению соответствует больший весовой коэффициент.
Кроме как перебором (тоесть разбить исходную область на элементарные и двигать
окружности в ней) идей решения на ум не приходит. Но этот способ черезчур затратный получается, особенно при увеличении количества окружностей и относительно большой исходной области. Если есть какие-нибудь соображения буду рад любой помощи.

Задача не учебная, так что принимаются любые решения.

[Gafield]

Сначала речь идет о шарах, а потом об окружностях?
Площадь пересечения, наверное, кругов?
Если координаты центров кругов фиксированны, то в чем задача?
А если нет, то решением будет совместить все круги.

[ZheniaM]

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

На плоскости расположены точки, у каждой из которых есть своя зона влияния (собственно окружность с радиусом $R$). Если пересекаются какие-либо 2 зоны влияния, то им приписывается коэффициент \alpha_2, если 3 и более, то коэффициент \alpha_3. Требуется так расставить точки в заданном множестве, обозначим его через $\Pi$ (пусть для начала прямоугольник с заданными размерами), чтобы:

Функционал качества макисмален

$$\alpha_1\sum_{i}S^1_i+\alpha_2\sum_{i}S^2_{i,j}+\alpha_3\sum_{i}S^3_{i,j,k}\to\max,$$

где $\alpha_1<\alpha_2<\alpha_3$, $\sum_{i}S^1_i - $ суммарная площадь зон влияния без пересечения с другими зонами, $\sum_{i,j}S^2_{i,j} - $ суммарная площадь зон влияния с одним пересечением в другой зоной и $\sum_{i,j,k}S^3_{i,j,k} - $ суммарная площадь зон влияния пересечения с 2 пересечениями.
При ограничении
S_\Pi-\sum_{i}S^1_i-\sum_{i}S^2_{i,j}-\sum_{i}S^3_{i,j,k}=\beta
( пространство без зон влияния вообще есть величина фиксированная)

В трёхмерном случае тоже самое, только зона влияния представляет собой сферу с радиусом $R$, а площади меняются на объёмы.

[Gafield]

Для точности: все-таки речь идет о кругах, а не об окружностях. Требования 1) и 2) вообще говоря, противоречивы. Если круги маленькие, то $\min$ доставляет набор попарно непересекающиеся кругов, а $\max$ - все с одним центром.

[ZheniaM]

Исправил предыдущее сообщение (заменил условие минимума на ограничение). Так даже более правильно.

[ddn]

ZheniaM писал(а):

Исправил предыдущее сообщение (заменил условие минимума на ограничение). Так даже более правильно.

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

[ZheniaM]

Случай, когда $M\to\infty$ меня мало интересует, так как задача практическая. Я понимаю, что это схожие задачи, но в данном случае всё усложняется тем, что возможны взаимные пересечения. Понятно, что решать скорей всего придётся полным перебором. Скажем разбить исходное множество на маленькие кусочки, и расставлять точки в них проверяя ограничения и считая функционал качества. Но тут возникает вопрос, а как его считать проще?..Понятно, что можно по методу Монте-Карло (накидать точек равномерно и посчитать количество вхождений точек в одну зону влияния в две и т.д.), но есть ли какой-нибудь другой способ?...Так как при таком случае задача становится почти не разрешимой.

Если, допустим, ограничится только случаем $S^2_{i,j}$?...Тоесть считать, что $S^2_{i,j}$ - это суммарная площадь при пересечении двух и более зон влияния. Тогда ставится вопрос, зная радиус этих зон и точки расположения можно ли как-нибудь её эффективно посчитать? Есть, конечно, формулы для нахождения площади пересечения двух окружностей, но вот есть ли для пересечения двух и более?...Или только полный перебор с Монте-Карло?