Задачу придумал буквально только что, пока ходил за водой на ручей.
На плоскости задан единичный круг. Требуется выбрать в этом круге N точек так, чтобы максимальное из расстояний от любой другой точки круга до ближайшей выбранной было минимальным. Если более математично, то нужно найти такие точки
,
чтобы величина
была минимальна, где C — единичный круг. Вопросы возникают такие. Каким будет это расстояние для различных N? Какие симметрии будут иметь получающиеся оптимальные множества для различных N?
Задачу пока не решал, но в простейших случаях решения, вроде, очевидны. Например, если точка одна, то её надо расположить в центре круга, тогда наиболее удалёнными точками будет граница круга, а искомое расстояние будет равно 1. Для двух точек ответ тоже очевиден: надо расположить их на границе диаметрально противоположно друг другу, тогда наиболее удалёнными будут точки на границе круга, искомое расстояние до которых будет равно
. Три точки надо расположить на границе круга в виде правильно треугольника, центр треугольника, а так же ещё три точки на границе, достраивающие выбранные до шестиугольника будут максимально удалёнными, а ответом на задачу будет снова 1. С четырьмя точками уже всё сложнее. И да, ответом на задачу при
, наверное, можно считать число 2.
Гугление на скорую руку привело к задаче плотной упаковки кругов и шаров, а так же вот к этой теме:
Равномерное распределение точек на диске. Это по смыслу близкие задачи, но мне кажется совсем другие.
Предлагаю поучаствовать в решении всем желающим!