Overlap of convex polytopes under rigid motion

Abstract

We present an algorithm to compute a rigid motion that approximately maximizes the volume of the intersection of two convex polytopes P-1 and P-2 in R-3. For all epsilon is an element of (0, 1/2] and for all n >= 1/epsilon, our algorithm runs in O(epsilon(-3) n log(3.5) n) time with probability 1 - n(-O(1)). The volume of the intersection guaranteed by the output rigid motion is a (1 - epsilon)-approximation of the optimum, provided that the optimum is at least lambda . max{vertical bar P-1 vertical bar . vertical bar P-2 vertical bar} for some given constant lambda is an element of (0, 1]. (C) 2013 Elsevier B.V. All rights reserved.