The minimum convex container of two convex polytopes under translations

Abstract

Given two convex d-polytopes P and Q in for , 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 a translate of Q that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension . The running time is , where n denotes the number of vertices of P and Q. In particular, in dimension , our algorithm runs in time. We also give an example of polytopes P and Q such that in the smallest container the translates of P and Q do not touch.