Minimum Convex Container of Two Convex Polytopes under Translations.
Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Dongwoo Park, Chan-Su Shin · 2014
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.