Extremal polygon containment problems (Q1330463)

A problem investigated in the article of the one in which a convex polygon has to be placed in an environment bounded by a collection of polygonal obstacles. Unlike previous algorithms in which fixed-size polygon placement was sought allowing its translation and rotation, here the largest copy of the polygon has to be placed in an environment allowing translation, rotation and scaling. To solve the problem the authors made use of efficient sequential and parallel algorithms for the fixed-size containment problem together with the parametric search technique originally introduced in \textit{N. Megiddo} [J. ACM 30, 9-31 (1987)]. They also demonstrated that the same approach can be used to solve several other similar extremal containment problems.