Let \(P\) and \(Q\) be two convex polygons in the plane. What is the minimum area of the convex hull of the union of these polygons if they are allowed to translate and rotate, but their interiors must not intersect? The authors present and analyse an algorithm which yields this area in \(O((n+m)nm)\) time, where \(n\) and \(m\) are the numbers of vertices of \(P\) and \(Q\), respectively.
To do this, they study the space of all configurations where \(P\) and \(Q\) touch each other. This space is divided into finitely many cells (the “mosaic map”), and it turns out that the area function can attain a minimum only at a finite number of special points. The algorithm then searches through these special points in an efficient way. The authors also report about the implementation and interesting test examples.