STACKING AND BUNDLING TWO CONVEX POLYGONS

Abstract

Given two compact convex sets C-1 and C-2 in the plane, we consider the problem of finding a placement phi C-1 of C-1 that minimizes the area of the convex hull of phi C-1 boolean OR C-2. We first consider the case where phi C-1 and C-2 are allowed to intersect (as in "stacking" two flat objects in a convex box), and then add the restriction that their interior has to remain disjoint (as when "bundling" two convex objects together into a tight bundle). In both cases, we consider both the case where we are allowed to reorient C-1, and where the orientation is fixed. In the case without reorientations, we achieve exact near-linear time algorithms, in the case with reorientations we compute a (1 + epsilon)-approximation in time O(epsilon(-1/2) log n+epsilon(-3/2) log epsilon(-1/2)), if two sets are convex polygons with n vertices in total.