The minimum convex container of two convex polytopes under translations

Abstract

Given two convex d-polytopes P and Q in R-d 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 a translate of Q that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension d 3. The running time is O(n((d-1)[d+1]/2)), where n denotes the number of vertices of P and Q. In particular, in dimension d = 3, our algorithm runs in O(n(4)) 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. (C) 2018 Elsevier B.V. All rights reserved.