Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 15:43 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2018, 15:08
Сообщений: 12
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Всем привет!

Заданы:
Множество окружностей 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 вот уже картинка не воспринимается совсем, и остается надеяться лишь на аналитическое решение.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 16:08 
Не в сети
Light & Truth
Зарегистрирован:
10 дек 2013, 02:33
Сообщений: 2306
Cпасибо сказано: 164
Спасибо получено:
293 раз в 284 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
НИЧЁССЕ!!!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 16:12 
Не в сети
Light & Truth
Зарегистрирован:
10 дек 2013, 02:33
Сообщений: 2306
Cпасибо сказано: 164
Спасибо получено:
293 раз в 284 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
задача скорей всего комбинаторная

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 16:18 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2018, 15:08
Сообщений: 12
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 16:25 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2018, 15:08
Сообщений: 12
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 16:49 
Не в сети
Light & Truth
Зарегистрирован:
10 дек 2013, 02:33
Сообщений: 2306
Cпасибо сказано: 164
Спасибо получено:
293 раз в 284 сообщениях
Очков репутации: 38

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 16:51 
Не в сети
Light & Truth
Зарегистрирован:
10 дек 2013, 02:33
Сообщений: 2306
Cпасибо сказано: 164
Спасибо получено:
293 раз в 284 сообщениях
Очков репутации: 38

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 17:04 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2018, 15:08
Сообщений: 12
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

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

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

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 17:09 
Не в сети
Light & Truth
Зарегистрирован:
10 дек 2013, 02:33
Сообщений: 2306
Cпасибо сказано: 164
Спасибо получено:
293 раз в 284 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
Кажется, начинает доходить.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислить макс количество пересекающихся окружностей
СообщениеДобавлено: 11 фев 2018, 17:13 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2018, 15:08
Сообщений: 12
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

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


Последний раз редактировалось Nikta_Danilov 11 фев 2018, 17:22, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2, 3  След.

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Условие ортогональности двух пересекающихся окружностей

в форуме Аналитическая геометрия и Векторная алгебра

Leka

3

531

29 май 2012, 09:11

Объединение пересекающихся эллипсов распред-я двумерной СВ

в форуме Теория вероятностей

kriteriy styudenta

0

196

16 фев 2014, 21:49

Найти макс./мин. значение выражения

в форуме Алгебра

Andrey8819

1

88

16 мар 2018, 10:18

Вычислить количество теплоты

в форуме Электричество и Магнетизм

TORT1

0

385

18 мар 2014, 22:04

Вычислить количество теплоты

в форуме Электричество и Магнетизм

TORT1

0

339

20 мар 2014, 20:09

Оптимизация капиталов. Ранжирование.формула макс А,при мин Б

в форуме Исследование операций и Задачи оптимизации

xcode

0

201

19 мар 2014, 11:46

Вычислить количество студентов в группе

в форуме Дискретная математика, Теория множеств и Логика

karastia_13

1

72

19 сен 2018, 11:22

Мин. и макс. площадь тре-ника по заданным двум радиусам

в форуме Интересные задачи участников форума MHP

TALMON

48

2591

04 мар 2013, 16:04

Методы моментов,макс.правдоп.,довер.интервал

в форуме Математическая статистика и Эконометрика

Yukkina

0

145

28 ноя 2016, 18:08

Выберите набор из макс. кол-ва линейно независимых векторов

в форуме Линейная и Абстрактная алгебра

forzi

23

167

13 июн 2018, 08:52


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved