Minimum Convex Container of Two Convex Polytopes under Translations

Given two convex d-polytopes P and Q in Rd for d ≥ 3, we study the problem of bundling P and Q in a smallest convex container. More precisely, our problem asks to find a minimum convex set containing P and Q that are in contact under translations. For dimension d = 3, we present the first exact algorithm that runs in O(n3) time, where n denotes the number of vertices of P and Q. Our approach easily extends to any higher dimension d> 3, resulting in the first exact algorithm