2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Покрытие диска/Disk covering problem
Сообщение02.01.2018, 17:58 
Аватара пользователя


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

На плоскости задан единичный круг. Требуется выбрать в этом круге 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
10908
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
4656
B@R5uk в сообщении #1280717 писал(а):
Например, если точка одна, то её надо расположить в центре круга, тогда наиболее удалёнными точками будет граница круга, а искомое расстояние будет равно 1. Для двух точек ответ тоже очевиден: надо расположить их на границе диаметрально противоположно друг другу, тогда наиболее удалёнными будут точки на границе круга, искомое расстояние до которых будет равно $\sqrt{2}$.

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

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


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

Изображение

$\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/
Забавно, что высокая симметрия не всегда даёт лучший результат. А ещё с двумя и тремя точками я сильно ошибся.

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


26/05/12
1694
приходит весна?
Некоторый прогресс в задаче был сделан за прошедшие годы. А ещё ссылка в предыдущем посте битая.

Интересно, что для 25 кругов оптимальное покрытие получается всё-таки очень симметричным:

Изображение

И радиус малого круга при единичном покрываемом можно посчитать по формуле (сам не проверял): $$r=\frac{1}{\sqrt{3}+\sqrt{6}}$$

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


07/08/23
1098
По ссылке про оптимальность ничего нет, это просто лучшее из найденных покрытий. Доказывать, что такие штуки на самом деле оптимальны, обычно сложно.

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


26/05/12
1694
приходит весна?
Ну да. Там указано, какие покрытия доказаны, кем и в каком году. Если верить страничке, то последнее было доказано в 2005 для десяти дисков.

Вот эта статья, если не ошибаюсь ("Thinnest Covering of a Circle by Eight, Nine, or Ten Congruent Circles" by Gábor Fejes Tóth). В ней автор ищет максимальный радиус диска, покрываемого единичными, и для $n=8,\;9,\;10_.$ показывает, что этот радиус равен $$r(n)=1+2\cos\left(\frac{2\pi}{n-1}\right)$$ Для семи дисков формула тоже работает, так как конфигурация остаётся той же.
Изображение Изображение


-- 11.08.2024, 10:11 --

Доказательство для пяти дисков, я так понимаю, на немецком. Интересно, на сколько оно велико.

Изображение

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

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



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

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


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

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