Calculating critical orientations of polyhedra for similarity measure evaluation

This paper studies a problem related to the computation of similarity measures for two convex polyhedra based on Minkowski sums and mixed volumes. To compute the similarity measure a function has to be evaluated over a number so-called critical relative orientations of these polyhedra. An open problem in this area concerns the case that three edges of one polyhedron are parallel to three different faces of the other, and can be formulated as the question in how many ways a given triple of spherical points in the slope diagram representation of one polyhedron can be made to coincide with three edges of the slope diagram representation of the second polyhedron by rotation. Here we show that this number, which was so far only known to be finite, is in fact at most eight by reducing the problem to the solution of an 8th degree equation in one variable, which can be solved numerically.