Overlap of convex polytopes under rigid motion

We present an algorithm to compute a rigid motion that approximately maximizes the volume of the intersection of two convex polytopes P1P1 and P2P2 in R3R3. For all ε∈(0,1/2]ε∈(0,1/2] and for all n⩾1/εn⩾1/ε, our algorithm runs in O(ε−3nlog3.5n) time with probability 1−n−O(1)1−n−O(1). The volume of the intersection guaranteed by the output rigid motion is a (1−ε)(1−ε)-approximation of the optimum, provided that the optimum is at least λ⋅max{|P1|,|P2|}λ⋅max{|P1|,|P2|} for some given constant λ∈(0,1]λ∈(0,1].