A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets
This work provides a fast and robust method for growth distance computation, which is useful for robotics and simulation applications requiring intersection and separation measures.
The paper presents an efficient algorithm for computing the growth distance between convex sets by reducing it to a ray intersection problem on the Minkowski difference set. The algorithm achieves state-of-the-art performance across a wide variety of convex sets, with applications in motion planning and rigid-body simulation.
In this paper, we discuss an efficient algorithm for computing the growth distance between two compact convex sets with representable support functions. The growth distance between two sets is the minimum scaling factor such that the sets intersect when scaled about some center points. Unlike the minimum distance between sets, the growth distance provides a unified measure for set intersection and separation. We first reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. Then, we propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. We show that our algorithm satisfies several key properties, such as primal and dual feasibility and monotone convergence. We provide extensive benchmark results for our algorithm and show that our open-source implementation achieves state-of-the-art performance across a wide variety of convex sets. Finally, we demonstrate robotics applications of our algorithm in motion planning and rigid-body simulation.