A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets

Akshay Thirugnanam; Koushil Sreenath

cs.ROApr 11, 2026

A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets

Authors: Akshay Thirugnanam, Koushil Sreenath

Organizations: Department of Mechanical Engineering, UC Berkeley, CA 94720, USA.

Abstract

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.

Figures & tables

Property	Internal Expanding procedure ( IE ), [ 16 ]	Differentiable Contact Features ( DCF ), [ 17 ]	Incremental algorithm ( Inc ), [ 18 ]	Differentiable Collisions ( DCol ), [ 19 ]	Our method
Types of convex sets	Convex primitives 1 , vertex meshes, DSFs	Differentiable Support Functions (DSFs)	Facet meshes	Convex primitives	Convex primitives, vertex meshes, DSFs
Algorithm outputs	Primal and dual optimal solutions	Primal and dual optimal solutions	Primal and dual optimal solutions	Primal optimal solution	Primal and dual optimal solutions
Solution guarantees	Primal and dual feasibility	Dual feasibility	Primal feasibility, compl. slackness	Dual feasibility	Primal and dual feasibility
Termination criterion	Primal-dual gap	Dual optimality error (gradient norm)	Dual infeasibility error	KKT error	Primal-dual gap
Warm start support	No	No	Yes	No	Yes

TABLE I: Comparison of Growth Distance Methods

Panel of Figure 2 — Fig. 1: Example of growth distance computation using ( 9 ) (in Fig. 1a ) and ray intersection computation using ( 10 ) (in Fig. 1b ). By Prop. 1 , the two problems are equivalent.

Notation	Reference	Definition
$\mathcal{C}$ , $p$	Prop. 1	Minkowski difference set, $\mathcal{C}=\mathcal{C}^{1}-\mathcal{C}^{2}+\{p^{2}-p^{1}\}$ , and center point difference, $p=p^{2}-p^{1}$ .
$s_{v}[\mathcal{C}]$ , $s_{p}[\mathcal{C}]$	( 2a ), ( 3 )	Support function and support point function, with $s_{v}[\mathcal{C}](\lambda)=\langle\lambda,s_{p}[\mathcal{C}](\lambda)\rangle$ .
$\alpha^{}$ , $\beta^{}$	( 9 ), ( 10 )	Growth distance and ray intersection value, $\beta^{}=1/\alpha^{}$ .
$\lambda_{k}$ , $v_{k}$ , $z_{k}$	Sec. III-A	Normal vector, support function value ( $v_{k}=s_{v}[\mathcal{C}](\lambda_{k-1})$ ), and support point ( $z_{k}=s_{p}[\mathcal{C}](\lambda_{k-1})$ ) at iteration $k$ .
$\mathcal{P}^{i}_{k}$ , $\mathcal{P}^{o}_{k}$	( 12 )	Inner and outer polyhedral approximations of $\mathcal{C}$ at iteration $k$ .
$M^{i}_{k}$ , $M^{o}_{k}$	( 12 )	Iteration index sets for the inner and outer polyhedral approximations at iteration $k$ .

TABLE II: Growth Distance Algorithm Notation

Panel of Figure 4 — Fig. 2: Examples of the growth distance algorithm state at the end of iteration $k$ , and after the inner and outer approximation update steps. The inner and outer approximations $\mathcal{P}^{i}_{k}$ and $\mathcal{P}^{o}_{k}$ are updated to better approximate the ray intersection point $\beta^{*}p$ and obtain an $\epsilon_{tol}$ -optimal solution to the ray intersection problem ( 10 ). Lastly, an $\epsilon_{tol}$ -optimal solution to the growth distance problem ( 9 ) is retrieved from the $\epsilon_{tol}$ -optimal solution to the ray intersection problem (see Prop. 1 ). Note that $p$ is constant during the algorithm execution.

Panel of Figure 5 — Fig. 3: Growth distance benchmark results for various types of convex sets, with cold and warm starts, across different methods. For each bar plot, the bars correspond to the $25$ -th, $50$ -th, and $75$ -th percentile values, and the whiskers show the $0.01$ and $99.99$ percentile values. The outliers are shown as dots. Our algorithm achieves state-of-the-art solution times for curved primitives and mesh sets (in cold start) across all existing methods. For DSFs, the hybrid Newton solver DCF proposed in [ 17 ] outperforms our algorithm. This is primarily because the DCF method requires fewer iterations to converge.

Benchmark case		Solution times: (median, $99.99$ -th percentile) in microseconds (‘ $-$ ’ means unsupported)
(cs: cold start, ws: warm start)		IE [ 16 ]	DCF [ 17 ]	Inc [ 18 ]	DCol [ 19 ]	Our method
Curved primitives	cs	$(2.83,6.86)$	$-$	$-$	$(7.61,21.4)$	$\bm{(1.86,4.60)}$
	ws	$-$	$-$	$-$	$-$	$\bm{(2.01,4.52)}$
Meshes	cs	$(1.79,6.15)$	$-$	$(3.93,22.4)$	$-$	$\bm{(1.33,4.70)}$
	ws	$-$	$-$	$\bm{(0.60,2.14)}$	$-$	$(0.69,3.57)$
DSFs [ 17 ]	cs	$(165,1390)$	$\bm{(94.4,848)}$	$-$	$-$	$(156,1300)$

TABLE III: Solution Times for Growth Distance Computation

Fig. 4: Solution times for growth distance computation using the interior-point method DCol [ 19 ] and our method, for polytopes with different numbers of vertices. For a given number of polytope vertices, the vertices are randomly generated from an ellipsoid surface with an aspect ratio equal to $10$ . The lines show the median solution times, and the shaded regions correspond to the minimum and maximum values. As the number of polytope vertices increases, the solution time for DCol (in blue) increases drastically. On the other hand, our method demonstrates (roughly) linear growth in solution time (in orange). When using the hill-climbing algorithm [ 5 ] to accelerate support function computation, we achieve sublinear growth in solution time (in green).

Panel of Figure 8 — Fig. 5: Convergence rate results for the growth distance algorithm, Alg. 3 , for $10^{7}$ function calls. The geometric parameters for the primitive sets are varied over two orders of magnitude. The mesh sets are generated identically to the method described in Fig. 4 . Our method achieves a linear worst-case convergence rate for primitive sets and finite convergence for mesh sets.

Fig. 6: Multi-rigid-body simulation of $50$ randomly generated polytopes falling on the ground, with our growth distance implementation used as the collision detection and contact frame computation backend in the Bullet Physics SDK. The polytopes with larger speeds are depicted in red, and the stationary polytopes in blue. The total kinetic energy of the system reaches zero at the end of $10\text{\,}\mathrm{s}$ . The maximum penetration depth across all collisions is $1.39\text{\,}\mathrm{c}\mathrm{m}$ , which is similar to the maximum penetration depth achieved using the default signed distance-based collision detector.

Fig. 7: Motion planning for a manipulator robot in a workspace with five tightly-placed obstacles. The red dots indicate the end-effector position. The robot’s state validity during motion planning is verified using our growth distance implementation.

Approximation Algorithms

Approximation algorithms find provably near-optimal solutions to computationally hard optimization problems when exact solutions are impractical.

See all 88 papers

Hölder Signed Distance: A Differentiable, Signed, Parallelizable Metric for Robotics
Aug 7, 2026Felipe Bartelt, Ali Umut Kaypak, Anthony Tzes +3Signed Distance Functions Differentiable Optimization
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Mar 19, 2026Tsuri Farhana, Omrit Filtser, Shalev GoldshteinMulti-Robot Motion Planning Approximation Algorithms
Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel
Sampling-based Certified Planning with Graphs of Convex Sets
Aug 30, 2026Peng Xie, Amr AlanwarConstrained Motion Planning Robotic Manipulation
TUM School of Computation, Information and Technology, Department of Computer Engineering, Technical University of Munich, 74076 Heilbronn, Germany

Aug 7, 2026J/K move · Enter open · S save

Hölder Signed Distance: A Differentiable, Signed, Parallelizable Metric for Robotics

Felipe Bartelt, Ali Umut Kaypak, Anthony Tzes, Farshad Khorrami+2

Signed Distance Functions Differentiable Optimization Robot Motion Planning

Open paper AskPDF arXiv

Computing distances between sets is essential in robotic motion planning and control, where differentiable gradients enable real-time optimization. The Euclidean Signed Distance Function (SDF), however, is not differentiable everywhere, and existing alternatives often sacrifice differentiability, sign information, or computational efficiency. In this letter, we introduce a novel differentiable signed distance between convex polyhedra. To this end, we first propose differentiable versions of the minimum and maximum operators, termed the Hölder minimum and Hölder maximum. We then replace the original min-max operators in the classical SDF formulation, yielding the Hölder signed distance. Unlike prior differentiable distance formulations that rely on iterative algorithms, our approach is computed in closed form, eliminating convergence issues while remaining naturally amenable to GPU parallelization. We validate the practical advantages and computational performance of the proposed distance through runtime comparisons with existing approaches. We also present a robotic manipulator experiment, demonstrating its suitability for applications in control.

Abstract

Approximation Algorithms

Explore similar work

Hölder Signed Distance: A Differentiable, Signed, Parallelizable Metric for Robotics

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

Sampling-based Certified Planning with Graphs of Convex Sets