Коротко и по сути — какие естественные критерии оптимальности можно поставить и какие численные методы для них подходят.
Критерии оптимальности (варианты формулировок)
- Максимальная вписанная площадь (максимум площади среди всех $n$-угольников внутри круга радиуса $R$):
$$\text{max}A(P),A(P)=\frac{1}{2}\sum _{i=1}^n(x_i{y}_{i+1}-x_{i+1}{y}_i).$$ Для вершин, лежащих на окружности радиуса $R$, оптимум — правильный $n$-угольник.
- Минимальная погрешность по Хаусдорфу:
$$\underset{P}{\min }{d}_H(P,C),d_H(P,C)=\max \{\underset{p\in P}{\sup }\underset{c\in C}{\inf }\Vert p-c\Vert ,\underset{c\in C}{\sup }\underset{p\in P}{\inf }\Vert c-p\Vert \}.$$ Для выпуклого $P$ и окружности часто редуцируется к радиальной ошибке ${\max }_{\theta }|r_P(\theta )-R|$. Для правильного вписанного $n$-угольника
$$e_{\max }=R(1-\cos (\frac{\pi }{n})),$$ а для правильного описанного (стороны касаются окружности)
$$e_{\max }=R(\sec (\frac{\pi }{n})-1).$$
- Минимальная максимальная радиальная ошибка (Chebyshev):
$$\underset{P}{\min }\underset{\theta \in [0,2\pi )}{\max }|r_P(\theta )-R|.$$ Это задача минимакс-приближения функции $R$ на окружности кусочно-функцией, задаваемой сторонами/вершинами многоугольника.
- Минимизация среднеквадратичной (L2) радиальной ошибки:
$$\underset{P}{\min }{\int }_0^{2\pi }(r_P(\theta )-R{)}^{2}d\theta .$$
- Ошибка по периметру / длине кривой:
$$\underset{P}{\min }|\text{perim}(P)-2\pi R|.$$
- Кривизна / распределение кривизны. Кривая окружности имеет постоянную кривизну $k=1/R$. У многоугольника кривизна сосредоточена в вершинах (дельта-функции). Можно минимизировать, например,
$$\underset{P}{\min }{\int }_0^{2\pi }(k_{ϵ}^P(\theta )-1/R{)}^{2}d\theta ,$$ где $k_{ϵ}^P$ — сглаженная кривая кривизны многоугольника (чтобы избежать сингулярностей). Альтернативно работать с опорной функцией $h(\theta )$: для выпуклой кривой $k(\theta )=1/(h(\theta )+h^{\prime \prime }(\theta ))$ и минимизировать отклонение $h$ от константы $R$.
- Комбинированные критерии (взвешенные суммы площади, Хаусдорфа, L2-кривизны и пр.).
Замечания по теоретическим свойствам
- Для многих из вышеуказанных критериев (площадь для вписанных, периметр и симметричные критерии) оптимальным является правильный $n$-угольник при условии симметрии/вершин на окружности.
- Для свободной (без условия «вершины на окружности») и несимметричной постановки оптимум может быть несинметричен и требует численного поиска.
Практические численные методы поиска
Параметризации (важно выбрать удобную):
- Координаты вершин $(x_i,y_i)$ (2n переменных) с ограничением порядка обхода и невырожденности (крест-продукт >0). Минус — сложные выпуклые/непересекающиеся ограничения.
- Полярная параметризация: радиусы $r_i$ в заданных направлениях ${\theta }_i$. Для выпуклой последовательности можно фиксировать равные ${\theta }_i$ и оптимизировать $r_i>0$.
- Опорная функция $h(\theta )$ заданная в $n$ направлениях (дискретизация). Для выпуклости достаточно линейных неравенств на вторые разности $h_{i-1}-2h_i+h_{i+1}\le 0$ (дискретная выпуклость).
- Параметризация углов между рёбрами (если вершины на окружности) — тогда остаётся параметр размещения вершин по углу.
Методы оптимизации по типу задачи
- Линейное программирование (LP): критерий минимакса радиальной ошибки с параметризацией радиусов/опорной функции можно свести к LP (линейные ограничения для каждой дискретной $\theta$ и цель минимизации максимума). Подходит для L^\infty.
- Квадратичное программирование (QP): L2-ошибка в дискретизации приводит к QP с линейными ограничениями (выпуклая задача).
- NLP (нелинейная оптимизация, SQP, L-BFGS-B): для задач с нелинейными критериями (кривизна, интегральные функции через $h,h^{\prime \prime }$) — использовать градиенты/якобианы. Рекомендуется вычислять аналитические производные (area/perimeter/радиус) или автоматическое дифференцирование.
- Глобальные эвристики (генетические алгоритмы, дифференциальная эволюция, simulated annealing): когда задача не выпуклая и много локальных минимумов.
- Комбинация: сначала глобальная эвристика для получения начального приближения, затем локальный градиентный метод для уточнения.
Числовые приёмы и стабильность
- Дискретизация круга: для L2 и L\infty интегралов берут сетку по $\theta$; при оптимизации гладко аппроксимируют операторы max через лог-sum-exp для возможности дифференцирования.
- Сглаживание кривизны: для критерия по кривизне нужно сгладить распределение кривизны (свертка гауссианом) или аппроксимировать многоугольник кривой класса $C^2$.
- Снижение размерности: при симметричных задачах винетирование симметрии (зафиксировать равные углы/радиусы) резко упрощает задачу.
- Ограничения выпуклости можно задавать в виде линейных неравенств на опорную функцию: это делает задачу удобной для конвексных методов.
- Начальная инициализация: правильный $n$-угольник — хорошая стартовая точка.
Примеры целевых формул (для регулярного вписанного $n$-угольника в окружность радиуса $R$):
- апофема $a=R\cos (\frac{\pi }{n})$;
- радиальная максимальная ошибка $e_{\max }=R(1-\cos (\frac{\pi }{n}))$;
- радиальная функция стороны (в интервале $|\varphi |\le \pi /n$, $\varphi$ относительно середины стороны):
$$r(\varphi )=\frac{R\cos (\frac{\pi }{n})}{\cos \varphi },$$ поэтому L2-ошибку можно вычислить через интеграл
$${\int }_{-\pi /n}^{\pi /n}(R-r(\varphi ){)}^{2}d\varphi$$ и умножить на $n$.
Рекомендации
- Если цель — «как можно ближе по форме» в смысле максимальной симметрии/площади/Хаусдорфа — начинайте с правильного $n$-угольника (он часто оптимален).
- Если критерий L^\infty или L^2 по радиальному отклонению — параметризация опорной функции + LP/QP эффективна и надежна.
- Если важна аппроксимация кривизны — используйте сглаживание и используйте нелинейные методы; ожидайте невыпуклость, используйте глобальный поиск + локальную оптимизацию.
Если нужно, могу:
- привести конкретную дискретную формулировку LP/QP для L^\infty/L^2,
- выписать выражения градиентов площади/погрешности по координатам вершин,
- или показать пример кода для численной оптимизации.