Кратко — задача: для выпуклого многоугольника $P\subset {\mathbb{R}}^2$ найти прямоугольник максимальной площади, вложенный в $P$.
Общие формулировки (используем в разных подходах)
- параметризация прямоугольника: центр $c=(x,y)$, ориентация $\theta$, полуоси $a,b>0$. множество точек прямоугольника
$$R(c,\theta ,a,b)=\{c+R(\theta )(u,v{)}^{\top }:u\in [-a,a],v\in [-b,b]\},$$ где $R(\theta )$ — матрица поворота. Площадь $\mathcal{A}=4ab$.
- выпуклый многоугольник задаётся системой полупространств $n_j^{\top }z\le d_j$ или вершинами $p_i$.
1) Аналитика в координатах (параметризация + НЛОП/KKT)
- формулировка: максимизировать $\mathcal{A}=4ab$ по переменным $(c,\theta ,a,b)$ при ограничениях «четыре угла прямоугольника лежат в $P$», т.е. для всех $j$ и всех комбинаций углов
$$n_j^{\top }(c+R(\theta )(\pm a,\pm b{)}^{\top })\le d_j.$$ - характер задачи: негладкая/не выпуклая НЛОП (перемножение $a\cdot b$ и нелинейная зависимость от $\theta$); можно применять градиентные методы, SQP, применять KKT для нахождения стационарных точек.
- плюсы: точная модель; допускает вычисление градиентов (автодифференцирование), быстрые локальные сходимости у хороших оптимизаторов; легко добавлять дополнительные ограничения.
- минусы: многомодальность (локальные максимумы), требуется хорошая инициализация; сложность оценки глобальной оптимальности; реализация требует НЛОП‑решателя и аккуратной обработки углов/особых случаев.
2) Вариационные / методы оптимизации по форме (shape optimization, level‑set, shape derivatives)
- идея: рассматривать функционал площади $J(\Omega )=\text{area}(\text{max rectangle inscribed in}\Omega )$ и проводить градиентный спуск в пространстве форм или эволюцию границы (level‑set) для оптимизации формы прямоугольника; или минимизировать отрицательную площади с ограничением «вложенности».
- математически требуют вычисления производных по форме (shape derivative) и учёта контактных условий (смешанные краевые условия).
- плюсы: естественно для гладких выпуклых областей, гибкость (можно работать с регуляризацией, гладким ограничением), получают эволюционные/стабильные схемы; подходят когда $P$ — аппроксимация гладкой области.
- минусы: сложная теория/реализация; обычно даёт только локальные экстремумы; вычислительно тяжёлые (решение PDE/эволюция уровня); в дискретном (многоугольник) случае менее прямолинейны чем метод с параметрами.
3) Методы перебора / комбинаторный / сканирование ориентаций
- идеи:
- дискретизация ориентации: для каждой $\theta$ прямоугольник со сторонами, параллельными направлениям $(\cos \theta ,\sin \theta )$ и $(-\sin \theta ,\cos \theta )$. Для фиксированной $\theta$ задача поиска наилучшего осесимметричного прямоугольника сводится к ограничению полупространствами в координатах $(u,v)$ и может быть решена как комбинаторическая проверка опорных линий (четыре поддерживающие прямые) либо как НЛОП небольшой размерности. Просканировав набор $\theta$ (или ключевые углы, где меняется комбинаторная структура), ищут глобальный максимум.
- перебор поддерживающих граней: рассмотреть какие ребра многоугольника служат опорными для четырёх сторон прямоугольника (комбинации граней/вершин) и для каждой комбинации решить линейную систему — генерировать кандидаты.
- rotating calipers / специализированные структуры: для некоторых видов прямоугольников (например, максимальная осесимметричная по осям параллельных координат) есть линейно‑логарифмические алгоритмы; для общего прямоугольника используют перебор комбинаций контактных граней.
- плюсы: часто простой и надёжный путь к глобальному оптимуму; дискретизация ориентации + локальная доработка (рефинемент) даёт практическое решение; подход комбинаторики даёт конечное число кандидатов (можно доказать, что структура меняется только в конечном числе углов).
- минусы: абс. перебор комбинаций может быть дорог (в худшем случае комбинаторика $O(n^k)$); дискретизация ориентации даёт приближённый ответ (точность зависит от сетки); требуется аккуратно учитывать вырожденные случаи. Для точного алгоритма приходится анализировать все перестановки поддерживающих граней (сложно реализовать).
Практические замечания и рекомендации
- задача НЕЛЬЗЯ считать выпуклой в переменных $(c,\theta ,a,b)$ из‑за произведения $ab$ и тригонометрии, поэтому глобальный поиск обычно комбинируют: сканирование по ориентации $\theta$ + для каждой $\theta$ решать низкоразмерную задачу (линейно/комбинаторно или НЛОП) и затем локальная доработка (SQP) от лучшей кандидатуры.
- для точного (гарантированного) решения имеет смысл рассмотреть разбиение пространства ориентаций на интервалы, где комбинаторная структура поддерживающих граней фиксирована; число таких интервалов полиномиально в $n$, что даёт алгоритм с конечной проверкой (сложно в реализации, но теоретически возможно).
- для практических задач: для малых/средних $n$ — перебор ориентаций, каждая проверка $O(n)$; для больших $n$ — приближённый метод (сэмплинг $\theta$ + локальная оптимизация). Для гладких областей — развернутые вариационные схемы если требуется регулярность.
Краткое сравнение по критериям
- точность/гарантии: комбинаторный/перебор (при полном переборе) > аналитика+НЛОП (локальная оптимальность) ≈ вариационные (локальная)
- сложность реализации: перебор/сканирование проще < аналитика+НЛОП < вариационные (самая сложная)
- вычислительная нагрузка: вариационные (высокая) ≥ НЛОП (зависит от итераций) > дискретизация/перебор (контролируемо через сетку)
- устойчивость к локальным минимумам: перебор с последующей точной проверкой лучше; чистые градиентные/вариационные методы уязвимы.
Вывод: для практической реализации рекомендую гибрид: сканировать ключевые ориентации (например, углы ребер и их комбинации), для каждой $\theta$ строить оптимальный осесимметричный прямоугольник (комбинаторная проверка опорных линий или небольшая НЛОП), затем улучшать лучший кандидат локальным НЛОП/SQP. Вариационные методы целесообразны при аппроксимации гладких областей и при необходимости регулярности решения.