Вычисление парных размещений геометрических объектов

Рассматривается задача плоского размещения пары многоугольников, стороны которых параллельны осям координат (ортоблоков), по критерию максимизации площади пересечения. Для ортоблоков с $m$ и $n$ вершинами разработан алгоритм нахождения оптимального размещения с временно́й $O(m^2n^2(m+n)\log (m+n))$ и емкостной $O(mn)$ оценками сложности. Для ортоблоков, выпуклых относительно координатных осей, соответствующие оценки снижены до $O(mn(m+n)^2)$ и $O(m+n)$. Предложены приближенные алгоритмы решения задачи.