Покрытие диска/Disk covering problem

[B@R5uk]

Задачу придумал буквально только что, пока ходил за водой на ручей.

На плоскости задан единичный круг. Требуется выбрать в этом круге 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.

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

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

[svv]

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

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

B@R5uk в сообщении #1280717 писал(а):

Три точки надо расположить на границе круга в виде правильно треугольника, центр треугольника, а так же ещё три точки на границе, достраивающие выбранные до шестиугольника будут максимально удалёнными, а ответом на задачу будет снова 1.

Можно уменьшить. Впишем в единичный круг равносторонний треугольник. Три точки расположим в серединах его сторон. Тогда три круга с центрами в этих точках и радиусами $\frac{\sqrt 3}{2}$ будут покрывать исходный круг. Это значит, что расстояние от любой точки исходного круга до ближайшей выбранной не превосходит $\frac{\sqrt 3}{2}$.

[g______d]

https://en.wikipedia.org/wiki/Disk_covering_problem

[Geen]

B@R5uk в сообщении #1280717 писал(а):

Например, если точка одна, то её надо расположить в центре круга, тогда наиболее удалёнными точками будет граница круга, а искомое расстояние будет равно 1. Для двух точек ответ тоже очевиден: надо расположить их на границе диаметрально противоположно друг другу, тогда наиболее удалёнными будут точки на границе круга, искомое расстояние до которых будет равно $\sqrt{2}$.

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

[B@R5uk]

Вот какие другие решения у меня получились:



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

[B@R5uk]

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

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



И радиус малого круга при единичном покрываемом можно посчитать по формуле (сам не проверял):

$$r=\frac{1}{\sqrt{3}+\sqrt{6}}$$

[dgwuqtj]

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

[B@R5uk]

Ну да. Там указано, какие покрытия доказаны, кем и в каком году. Если верить страничке, то последнее было доказано в 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 --

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