Reducing the time complexity of Minkowski-sum based similarity calculations by using geometric inequalities

The similarity of two convex polyhedra A and B may be calculated by evaluating the volume or mixed volume of their Minkowski sum over a specific set of relative orientations. The relative orientations are characterized by the fact that faces and edges of A and B are parallel as much as possible. For one of these relative orientations the similarity measure is optimal. In this article we propose and test a method to reduce the number of relative orientations to be considered by using geometric inequalities in the slope diagrams of A and B. In this way the time complexity of O(n(6)) is reduced to O(n(4.5)). This is derived, and verified experimentally.