Solving the interference problem for ellipses and ellipsoids: new formulae (Q2075971)

Ellipses and ellipsoids are essential entities for modelling (and/or enclosing) the shape of the objects under consideration. So, in this sense, the problem of detecting when two moving ellipses or ellipsoids overlap is of interest to robotics, CAD/CAM, computer animation, etc. In this paper, the authors consider the characteristic polynomial of the pencil defined by two ellipses/ellipsoids \(A\) and \(B\) given by \(X^T AX = 0\) and \(X^T BX = 0\) and they analyze symbolically the sign of the real roots of the characteristic polynomial. From this, new formulae are derived when \(A\) and \(B\) overlap, are separate, or touch each other externally. This characterization is defined by a minimal set of polynomial inequalities depending only on the entries of \(A\) and \(B\). Thus, one of the fascinating result of this paper is that one needs only to compute the characteristic polynomial of the pencil defined by \(A\) and \(B\), det\((TA + B)\), and not the intersection points between them. The authors compare the results with the best available approach dealing with this problem, and they show that the new formulae involve a smaller set of polynomials and less sign conditions. Finally, as an application, it is shown that, since the analysis of the univariate polynomials (depending on the time) in the formulae provides the collision events between them, the obtained characterization provides a new approach for exact collision detection of two moving ellipses or ellipsoids.