Largest triangles in a polygon (Q2230417)

The authors consider the following problem: Suppose we are given a simple polygon \(P\) in the plane and a set \(\mathcal{S}\) of triangles, find a triangle \(T\) that has maximal area under the following constraints: \begin{itemize} \item \(T\) is inscribed in \(P\), and \item \(T\) is up to rotations, translations and scalings equivalent to a triangle in \(\mathcal{S}\). \end{itemize} The authors present an exact algorithm for computing \(T\), when \(\mathcal{S}\) consists of a single triangle. In addition, several variants of the above problem are investigated. For example, \begin{itemize} \item the container polygon~\(P\) is additionally assumed to be convex, \item the set~\(\mathcal{S}\) consists of a triangle and the reflection of this triangle, \item the set~\(\mathcal{S}\) consists of all triangles that have a corner with some fixed interior angle~\(\alpha\), and/or \item the area of \(T\) is not maximal, but only requires to be at least \((1-\varepsilon)\) times the maximal possible area for some given \(0<\varepsilon<1\). \end{itemize} The main results are presented in terms of time/space complexities. The problems are of interest in pattern recognition, computer vision and computational geometry.