The Containment Polytope of a Triangle and a Convex Polygon

Abstract

The containment polytope $\mathcal{C}$ for a triangle $P$ and a convex $n$-gon $Q$ is a four-dimensional polytope representing the similarity transforms (translation, rotation, scaling) that place $P$ inside $Q$. While it is known that the complexity of $\mathcal{C}$ and its silhouette $Λ$, which represents all the largest placements of $P$ inside $Q$ for all orientations, can be quadratic in $n$, we show that the silhouette can be partitioned into a linear number of planar convex chains and steps in $O(n \log n)$ time. Based on the linear number of convex chains and steps, we can compute the complexity of silhouette $Λ$ in $O(n \log n)$ time and query the largest placement of $P$ inside $Q$ for a given orientation in $O(\log n)$ time. We explain geometrically how the triangle $P$ rotates while continuously scaling and translating to be maximal inside $Q$, leading to a parameterized algorithm for containment problems.