Математический форум Math Help Planet
http://mathhelpplanet.com/

Вычислить макс количество пересекающихся окружностей
http://mathhelpplanet.com/viewtopic.php?f=31&t=58116
Страница 1 из 3

Автор:  Nikta_Danilov [ 11 фев 2018, 15:43 ]
Заголовок сообщения:  Вычислить макс количество пересекающихся окружностей

Всем привет!

Заданы:
Множество окружностей E, выраженных множеством пар координат [math]e_{i} = (x,y)[/math], где координаты [math]\in N[/math].
r - радиус, одинаковый для всех окружностей.
d - дистанция пересечения, минимальное расстояние между центрами двух любых окружностей, при которой окружности начинают считаться пересекающимися.

Необходимо вычислить n - максимальное количество пересекающихся окружностей, с учетом r и d.
Не нашел способа лучше выразить его, кроме как мощность множества:
[math]n = \left| \left{ e_{i} | \forall e_{j} \in E, \sqrt{ \left( x_{i} - x_{j} \right)^{2} + \left( y_{i} - y_{j} \right)^{2} } < r \right} \right| \to max[/math]
(формулу не получается починить, картинка ниже)
Изображение

Фактически, надо найти как наиболее плотно смогут разместиться окружности при заданных условиях.
При d=r это прорисовывается вручную несложно:
Изображение
При d=r/2 и d=r/4 вот уже картинка не воспринимается совсем, и остается надеяться лишь на аналитическое решение.

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

Автор:  sergebsl [ 11 фев 2018, 16:08 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

НИЧЁССЕ!!!

Автор:  sergebsl [ 11 фев 2018, 16:12 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

задача скорей всего комбинаторная

Вам нужно вычилить число всевозможных точек пересечений или число пар пересекающихся окружностей?

Автор:  Nikta_Danilov [ 11 фев 2018, 16:18 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

sergebsl писал(а):
задача скорей всего комбинаторная
Вам нужно вычилить число всевозможных точек пересечений или число пар пересекающихся окружностей?


При конкретных данных - вычислить такую точку на координатной плоскости, которая "накрыта" наибольшим количеством окружностей радиуса d, скорее как то так.
При определении предела - получается понять как наиболее плотно можно так разместить окружности.

Автор:  Nikta_Danilov [ 11 фев 2018, 16:25 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

На реальных данных я это считаю в цикле - прохожу по всем парам координат, и для каждой вычисляю количество других окружностей до которых расстояние меньше d.
Но мне не дает (и не дают) покоя вопрос - а каков предел будет в общем случае.

Автор:  sergebsl [ 11 фев 2018, 16:49 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

Nikta_Danilov писал(а):
На реальных данных я это считаю в цикле - прохожу по всем парам координат, и для каждой вычисляю количество других окружностей до которых расстояние меньше d.
Но мне не дает (и не дают) покоя вопрос - а каков предел будет в общем случае.


так как рисунок получается регулярный(Повторяющийся), то на всей плоскости предела этому не будет.

Автор:  sergebsl [ 11 фев 2018, 16:51 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

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

Автор:  Nikta_Danilov [ 11 фев 2018, 17:04 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

sergebsl писал(а):
так как рисунок получается регулярный(Повторяющийся), то на всей плоскости предела этому не будет.

Но пересекаются ведь не все со всеми?

Для удобства графического решения предлагаю принять [math]r \to d[/math], т.е. просто для построения - две окружности могут находиться на расстоянии радиуса друг от друга, но ни на йоту ближе.
Тогда, на рисунке получается n=7, как например для окружности в центре - точно через её центр проходят еще 6 окружностей и нигде невозможно большее скопление окружностей.
Этот случай доказывается вполне аналитически - максимум можно разместить 6 точек на окружности так, чтобы между всеми ними было расстояние = радиусу.

sergebsl писал(а):
Прошу прощения, я не совсем вник в вашу проблему. Поэтому ответы могу давать неточные.


Да я рад что есть хотя бы примерно с кем обсудить :) В ближайшем окружении люди имеют другую специализацию.
Возможно, я и сам зациклился на одном представлении проблемы, но попытки выразить её через формулы окружностей результатов пока не дали.

Автор:  sergebsl [ 11 фев 2018, 17:09 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

Кажется, начинает доходить.

Завтра, наверное, точно дойдёт)))

Автор:  Nikta_Danilov [ 11 фев 2018, 17:13 ]
Заголовок сообщения:  Re: Вычислить макс количество пересекающихся окружностей

Только для этого отдельно рассматриваемого случая, в принципе, важно только значение [math]d[/math] которое и можно считать за радиус.

UPDATE: Удалил неправильную мысль из этого поста.

Страница 1 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/