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
10887
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
1055
По ссылке про оптимальность ничего нет, это просто лучшее из найденных покрытий. Доказывать, что такие штуки на самом деле оптимальны, обычно сложно.

 Профиль  
                  
 
 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 ] 

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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