Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 3 |
[ Сообщений: 29 ] | На страницу 1, 2, 3 След. |
|
Автор | Сообщение | |
---|---|---|
Nikta_Danilov |
|
|
Заданы: Множество окружностей 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 |
|
|
НИЧЁССЕ!!!
|
||
Вернуться к началу | ||
sergebsl |
|
|
задача скорей всего комбинаторная
Вам нужно вычилить число всевозможных точек пересечений или число пар пересекающихся окружностей? |
||
Вернуться к началу | ||
Nikta_Danilov |
|
|
sergebsl писал(а): задача скорей всего комбинаторная Вам нужно вычилить число всевозможных точек пересечений или число пар пересекающихся окружностей? При конкретных данных - вычислить такую точку на координатной плоскости, которая "накрыта" наибольшим количеством окружностей радиуса d, скорее как то так. При определении предела - получается понять как наиболее плотно можно так разместить окружности. |
||
Вернуться к началу | ||
Nikta_Danilov |
|
|
На реальных данных я это считаю в цикле - прохожу по всем парам координат, и для каждой вычисляю количество других окружностей до которых расстояние меньше d.
Но мне не дает (и не дают) покоя вопрос - а каков предел будет в общем случае. |
||
Вернуться к началу | ||
sergebsl |
|
|
Nikta_Danilov писал(а): На реальных данных я это считаю в цикле - прохожу по всем парам координат, и для каждой вычисляю количество других окружностей до которых расстояние меньше d. Но мне не дает (и не дают) покоя вопрос - а каков предел будет в общем случае. так как рисунок получается регулярный(Повторяющийся), то на всей плоскости предела этому не будет. |
||
Вернуться к началу | ||
sergebsl |
|
|
Прошу прощения, я не совсем вник в вашу проблему. Поэтому ответы могу давать неточные.
|
||
Вернуться к началу | ||
Nikta_Danilov |
|
|
sergebsl писал(а): так как рисунок получается регулярный(Повторяющийся), то на всей плоскости предела этому не будет. Но пересекаются ведь не все со всеми? Для удобства графического решения предлагаю принять [math]r \to d[/math], т.е. просто для построения - две окружности могут находиться на расстоянии радиуса друг от друга, но ни на йоту ближе. Тогда, на рисунке получается n=7, как например для окружности в центре - точно через её центр проходят еще 6 окружностей и нигде невозможно большее скопление окружностей. Этот случай доказывается вполне аналитически - максимум можно разместить 6 точек на окружности так, чтобы между всеми ними было расстояние = радиусу. sergebsl писал(а): Прошу прощения, я не совсем вник в вашу проблему. Поэтому ответы могу давать неточные. Да я рад что есть хотя бы примерно с кем обсудить В ближайшем окружении люди имеют другую специализацию. Возможно, я и сам зациклился на одном представлении проблемы, но попытки выразить её через формулы окружностей результатов пока не дали. |
||
Вернуться к началу | ||
sergebsl |
|
|
Кажется, начинает доходить.
Завтра, наверное, точно дойдёт))) |
||
Вернуться к началу | ||
Nikta_Danilov |
|
|
Только для этого отдельно рассматриваемого случая, в принципе, важно только значение [math]d[/math] которое и можно считать за радиус.
UPDATE: Удалил неправильную мысль из этого поста. Последний раз редактировалось Nikta_Danilov 11 фев 2018, 17:22, всего редактировалось 1 раз. |
||
Вернуться к началу | ||
На страницу 1, 2, 3 След. | [ Сообщений: 29 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |