Simple but not Simpler: A Surface-Sliding Method for Finding the Minimum Distance between Two Ellipsoids
This incremental method addresses a specific computational geometry problem for applications in computer graphics, engineering design, material modeling, and scientific simulations.
The paper tackles the problem of finding the minimum distance between two ellipsoids by proposing a novel iterative surface-sliding method, achieving excellent numerical performance in accuracy, consistency, stability, and robustness.
We propose a novel iterative process to establish the minimum separation between two ellipsoids. The method maintains one point on each surface and updates their locations in the theta-phi parametric space. The tension along the connecting segment between the two surface points serves as the guidance for the sliding direction, and the distance between them decreases gradually. The minimum distance is established when the connecting segment becomes perpendicular to the ellipsoid surfaces, at which point the net effect of the segment tension disappears and the surface points no longer move. Demonstration examples are carefully designed, and excellent numerical performance is observed, including accuracy, consistency, stability, and robustness. Furthermore, compared to other existing techniques, this surface-sliding approach has several attractive features, such as clear geometric representation, concise formulation, a simple algorithm, and the potential to be extended straightforwardly to other situations. This method is expected to be useful for future studies in computer graphics, engineering design, material modeling, and scientific simulations.