2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Равномерное дискретное распределение. Давайте решать вместе!
Сообщение02.01.2018, 17:58 
Аватара пользователя


26/05/12
1534
приходит весна?
Задачу придумал буквально только что, пока ходил за водой на ручей.

На плоскости задан единичный круг. Требуется выбрать в этом круге N точек так, чтобы максимальное из расстояний от любой другой точки круга до ближайшей выбранной было минимальным. Если более математично, то нужно найти такие точки $P_k$, $k = 1, ... , N$ чтобы величина $$D=\underset{Q\in C}{\mathop{\max }}\,\underset{k=1}{\overset{N}{\mathop{\min }}}\,dist\left( Q,{{P}_{k}} \right)$$была минимальна, где C — единичный круг. Вопросы возникают такие. Каким будет это расстояние для различных N? Какие симметрии будут иметь получающиеся оптимальные множества для различных N?

Задачу пока не решал, но в простейших случаях решения, вроде, очевидны. Например, если точка одна, то её надо расположить в центре круга, тогда наиболее удалёнными точками будет граница круга, а искомое расстояние будет равно 1. Для двух точек ответ тоже очевиден: надо расположить их на границе диаметрально противоположно друг другу, тогда наиболее удалёнными будут точки на границе круга, искомое расстояние до которых будет равно $\sqrt{2}$. Три точки надо расположить на границе круга в виде правильно треугольника, центр треугольника, а так же ещё три точки на границе, достраивающие выбранные до шестиугольника будут максимально удалёнными, а ответом на задачу будет снова 1. С четырьмя точками уже всё сложнее. И да, ответом на задачу при $N=0$, наверное, можно считать число 2.

Гугление на скорую руку привело к задаче плотной упаковки кругов и шаров, а так же вот к этой теме: Равномерное распределение точек на диске. Это по смыслу близкие задачи, но мне кажется совсем другие.

Предлагаю поучаствовать в решении всем желающим! :D

 Профиль  
                  
 
 Re: Равномерное дискретное распределение. Давайте решать вместе!
Сообщение02.01.2018, 20:26 
Заслуженный участник


23/07/08
10626
Crna Gora
То есть покрыть единичный круг $N$ кругами минимального радиуса (одного и того же для всех покрывающих кругов).

-- Вт янв 02, 2018 20:04:16 --

B@R5uk в сообщении #1280717 писал(а):
Три точки надо расположить на границе круга в виде правильно треугольника, центр треугольника, а так же ещё три точки на границе, достраивающие выбранные до шестиугольника будут максимально удалёнными, а ответом на задачу будет снова 1.
Можно уменьшить. Впишем в единичный круг равносторонний треугольник. Три точки расположим в серединах его сторон. Тогда три круга с центрами в этих точках и радиусами $\frac{\sqrt 3}{2}$ будут покрывать исходный круг. Это значит, что расстояние от любой точки исходного круга до ближайшей выбранной не превосходит $\frac{\sqrt 3}{2}$.

 Профиль  
                  
 
 Re: Равномерное дискретное распределение. Давайте решать вместе!
Сообщение02.01.2018, 21:38 
Заслуженный участник
Аватара пользователя


08/11/11
5940
https://en.wikipedia.org/wiki/Disk_covering_problem

 Профиль  
                  
 
 Re: Равномерное дискретное распределение. Давайте решать вместе!
Сообщение02.01.2018, 21:47 
Заслуженный участник
Аватара пользователя


01/09/13
4318
B@R5uk в сообщении #1280717 писал(а):
Например, если точка одна, то её надо расположить в центре круга, тогда наиболее удалёнными точками будет граница круга, а искомое расстояние будет равно 1. Для двух точек ответ тоже очевиден: надо расположить их на границе диаметрально противоположно друг другу, тогда наиболее удалёнными будут точки на границе круга, искомое расстояние до которых будет равно $\sqrt{2}$.

А чего же это при добавлении точки $D$ увеличилось?

 Профиль  
                  
 
 Re: Равномерное дискретное распределение. Давайте решать вместе!
Сообщение02.01.2018, 23:20 
Аватара пользователя


26/05/12
1534
приходит весна?
Вот какие другие решения у меня получились:

Изображение

$\begin{matrix}
   N & 3 & 4 & 5 & 6  \\
   d & 1 & \frac{1}{\sqrt{2}} & \frac{\sqrt{5}-1}{2} & \frac{1}{\sqrt{3}}  \\
\end{matrix}$

-- 03.01.2018, 00:20 --

g______d в сообщении #1280783 писал(а):
Disk covering problem
Надо ознакомиться. Что-то там у них не совпадают значения с моими.

-- 03.01.2018, 01:04 --

Нашёл несколько картинок с решениями: http://www2.stetson.edu/~efriedma/circovcir/
Забавно, что высокая симметрия не всегда даёт лучший результат. А ещё с двумя и тремя точками я сильно ошибся.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group