Bundling three convex polygons to minimize area or perimeter (Q902419)

The problem of packing certain geometric shapes in Euclidean space to provide an optimal arrangement in some sense (e.g. the densest packing) is an interesting problem that has attracted attention of geometers since the time of Kepler. Typically, the shapes to be arranged belong to the same family (polygons, disks, spheres, ...). The general packing problem with containment starts with given \(k\) objects, and the task is to find the smallest region of a required shape (disk, rectangle, etc.) called a container so that the given objects can be packed in that region by means of suitable translations (for each object one), with the requirement that the translates are non-overlapping. Whatever algorithms are devised to effect such optimal packing, the question about comparative times of such algorithms is always important. For example, V. Milenkovic studied the packing of a set of polygons in the plane into a polygonal container and produced a \(O(n^{k-1} \log n)\)-time algorithm for packing \(k\) convex \(n\)-gons under translations into a minimum-area axis-parallel rectangular container [\textit{V. J. Milenkovic}, in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC '96. Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM. 109--118 (1996; Zbl 0922.68129)]. Another problem related to the packing problem is a bundling problem, whereby one is required to find a translation for each of given \(k\)-objects so that their translated positions are pairwise disjoint and the area or perimeter of their convex hull is minimized. For \(k =2,\) \textit{H. Lee} and \textit{T. Woo} [``Determining in linear time the minimum area convex hull of two polygons'', IIE Trans. 20, No. 4, 338--345 (1988; \url{doi:10.1080/07408178808966189})] devised a linear time algorithm for finding translations of two polygons that minimizes the area of the convex hull of their translates, and their algorithm can be adapted to the situation where the perimeter of the convex hull is to be minimized. In the paper under review the authors are concerned with the problem of finding a translation for each of three given polygons (having \(n\) vertices in total) such that the translated polygons are pairwise disjoint and the area or perimeter of their convex hull is minimized. Their method produces an algorithm for minimizing convex hull, which is the first \(O(n^2)\)-time algorithm that finds optimal translations of input polygons in such scenario.