Minimum Convex Hull and Maximum Overlap of Two Convex Polytopes

We study the problem of minimizing the convex hull of two convex polytopes with n vertices in total under translation in d-dimensional space ℝd for any fixed dimension d ≥ 2. For d ≥ 2, we present a deterministic O (n )-time algorithm returning a translation minimizing the area of the convex hull, improving upon the previously best O (n log n )-time algorithm. Our algorithm returns the smallest area of convex hulls under translation in the same time, and thus it is optimal. For d ≥ 3, we present a deterministic algorithm with running time O (n(d +1)/2) for odd d and O (nd /2 logd n ) for even d. This improves substantially upon the previously best algorithm by a factor at least n(d -1)/2 log n. We also consider the variant that two input polytopes are restricted to remain disjoint, and present a deterministic algorithm with running time O (nd+1) for odd d and O (nd logd -1 n) for even d. This improves substantially upon the previously best algorithm for d > 3 by factor nO (d2) We also study the problem of maximizing the overlap of two convex polytopes under translation in d-dimensional space ℝd for d ≥ 3. We give an -time algorithm, improving substantially upon the previously best algorithm by a factor at least n1-3/d logd +1 n.