pith. sign in

arxiv: 2604.10058 · v1 · submitted 2026-04-11 · 💻 cs.RO · cs.CG

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

Akshay Thirugnanam , Koushil Sreenath This is my paper

Pith reviewed 2026-05-10 16:19 UTC · model grok-4.3

classification 💻 cs.RO cs.CG
keywords growth distanceconvex setsMinkowski differenceray intersectionpolyhedral approximationmotion planningrobotics
0
0 comments X

The pith

A ray intersection algorithm computes growth distance between convex sets by approximating their Minkowski difference with polyhedra.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops an efficient method to calculate the growth distance between two compact convex sets that have representable support functions. The growth distance measures the smallest scaling needed around center points to make the sets touch or overlap, offering a single value for cases where sets are separate or intersecting. The authors reduce this computation to finding the point where a ray hits the Minkowski difference of the two sets. They solve the ray intersection by building successive inner and outer polyhedral approximations to the difference set. The approach is shown to be feasible at every step, to converge monotonically, and to run faster than prior methods on many examples, with uses in robot motion planning and physics simulation.

Core claim

We reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. We then propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. This algorithm satisfies primal and dual feasibility and monotone convergence.

What carries the argument

Iterative construction of inner and outer polyhedral approximations to the Minkowski difference set for solving the ray intersection problem.

If this is right

  • The algorithm maintains primal and dual feasibility in all iterations.
  • The approximations converge monotonically to the solution.
  • Benchmark results show state-of-the-art performance on a wide variety of convex sets.
  • The method supports applications in motion planning and rigid-body simulation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The open-source implementation can be used to benchmark against new convex set representations.
  • This method could inspire similar approximation techniques for other distance measures in computational geometry.
  • For robotics, faster growth distance might improve real-time collision avoidance in dynamic environments.

Load-bearing premise

The convex sets have compact shapes and their support functions can be represented in a form that allows polyhedral approximation.

What would settle it

A test case with two convex sets where the computed growth distance does not match the value obtained from a different reliable method, such as for two axis-aligned boxes.

Figures

Figures reproduced from arXiv: 2604.10058 by Akshay Thirugnanam, Koushil Sreenath.

Figure 1
Figure 1. Figure 1: Example of growth distance computation using (9) (in Fig. 1a) [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Examples of the growth distance algorithm state at the end [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Growth distance benchmark results for various types of convex [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Solution times for growth distance computation using the interior [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Convergence rate results for the growth distance algorithm, Alg. 3, [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 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 s. The maximum penetratio… view at source ↗
Figure 7
Figure 7. Figure 7: Motion planning for a manipulator robot in a workspace with five tightly-placed obstacles. The red dots indicate the end-effector position. The [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes an algorithm for computing the growth distance between two compact convex sets with representable support functions. It reduces the problem to an equivalent ray intersection problem on the Minkowski difference set, then solves it by iteratively constructing inner and outer polyhedral approximations. The authors assert that the algorithm satisfies primal-dual feasibility and monotone convergence, provide benchmark results claiming state-of-the-art performance with an open-source implementation, and demonstrate applications in motion planning and rigid-body simulation.

Significance. If the reduction to ray intersection, convergence properties, and performance claims hold, the work could provide an efficient alternative for unified intersection/separation measures in robotics, complementing methods like GJK and EPA. The open-source implementation and extensive benchmarks across convex sets are positive features that support reproducibility.

major comments (2)
  1. [Abstract and §4 (Benchmarks)] Abstract and performance evaluation section: the state-of-the-art performance claim depends on repeated support function evaluations of the input sets, but no analysis, bounds, or verification is provided on the computational cost of these oracles for the 'wide variety' of tested convex sets. If oracle evaluation requires numerical optimization (as is common for non-polyhedral bodies), the per-iteration cost may dominate and the advantage over existing methods is not established by the ray-intersection procedure alone.
  2. [§3 (Algorithm)] Algorithm description section: primal-dual feasibility and monotone convergence are asserted for the iterative polyhedral approximation scheme, but no derivation steps, error analysis for approximate oracles, or handling of numerical precision in ray intersections are supplied. These properties are load-bearing for the central claims yet cannot be verified from the given material.
minor comments (2)
  1. [Notation and preliminaries] Ensure all notation for scaling factors, centers, and Minkowski difference is introduced consistently before first use.
  2. [§4 (Benchmarks)] Benchmark tables would benefit from explicit reporting of support function evaluation times to allow readers to assess the oracle cost contribution.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below and outline the revisions we will make to strengthen the presentation of our results.

read point-by-point responses

  1. Referee: [Abstract and §4 (Benchmarks)] Abstract and performance evaluation section: the state-of-the-art performance claim depends on repeated support function evaluations of the input sets, but no analysis, bounds, or verification is provided on the computational cost of these oracles for the 'wide variety' of tested convex sets. If oracle evaluation requires numerical optimization (as is common for non-polyhedral bodies), the per-iteration cost may dominate and the advantage over existing methods is not established by the ray-intersection procedure alone.

    Authors: We agree that the performance claims are empirical and rely on the efficiency of the support-function oracles for the specific convex sets in our benchmarks. For the tested families (polytopes, ellipsoids, zonotopes, and superellipsoids), the oracles admit closed-form or low-cost evaluations, and our reported timings reflect total wall-clock time including oracle calls. The algorithm's contribution is to minimize the number of such calls while guaranteeing primal-dual feasibility. We will add a dedicated paragraph in §4 that tabulates the per-call cost of each oracle used, cites the relevant closed-form expressions, and explicitly notes that for bodies whose support functions require iterative numerical optimization the per-iteration overhead must be considered separately. This addition will clarify the scope of the state-of-the-art claim without altering the reported benchmark numbers. revision: partial

  2. Referee: [§3 (Algorithm)] Algorithm description section: primal-dual feasibility and monotone convergence are asserted for the iterative polyhedral approximation scheme, but no derivation steps, error analysis for approximate oracles, or handling of numerical precision in ray intersections are supplied. These properties are load-bearing for the central claims yet cannot be verified from the given material.

    Authors: We acknowledge that the current manuscript states these properties without supplying the full derivation or numerical-stability discussion. In the revised version we will expand §3 with a self-contained subsection that (i) derives primal-dual feasibility from the supporting-hyperplane construction at each iteration, (ii) proves monotone convergence of the inner and outer approximations to the true ray-intersection point under exact oracles, and (iii) provides a first-order error bound when the support-function oracle is only approximate. We will also add a short paragraph on floating-point handling of the ray-intersection test, referencing the robust predicate techniques already present in our open-source implementation. These additions will make the theoretical claims verifiable from the text. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation reduces growth distance to independent ray-intersection reformulation with proven convergence properties

full rationale

The paper's core chain begins with an explicit geometric reduction of growth distance to ray intersection on the Minkowski difference, followed by an iterative polyhedral approximation algorithm whose feasibility and monotone convergence are shown directly from the construction. No equation equates a claimed result to a fitted parameter or self-referential definition, and no load-bearing step relies on a self-citation whose content is unverified. Benchmarks are presented as empirical validation rather than part of the derivation. The support-function oracle assumption is stated as a problem-class precondition but does not render the algorithm tautological.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard convex-geometry assumptions rather than new free parameters or invented entities.

axioms (1)
  • domain assumption The input sets are compact and convex with representable support functions
    Explicitly required by the problem statement in the abstract.

pith-pipeline@v0.9.0 · 5456 in / 1122 out tokens · 40481 ms · 2026-05-10T16:19:56.814707+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Distance functions and their application to robot path planning in the presence of obstacles,

    E. Gilbert and D. Johnson, “Distance functions and their application to robot path planning in the presence of obstacles,”IEEE Journal on Robotics and Automation, vol. 1, no. 1, pp. 21–30, 2003

    work page 2003

  2. [2]

    Real-time (self)-collision avoidance task on a hrp-2 humanoid robot,

    O. Stasse, A. Escande, N. Mansard, S. Miossec, P. Evrard, and A. Kheddar, “Real-time (self)-collision avoidance task on a hrp-2 humanoid robot,” in2008 ieee international conference on robotics and automation. IEEE, 2008, pp. 3200–3205

    work page 2008

  3. [3]

    Motion planning with sequential convex optimization and convex collision checking,

    J. Schulman, Y . Duan, J. Ho, A. Lee, I. Awwal, H. Bradlow, J. Pan, S. Patil, K. Goldberg, and P. Abbeel, “Motion planning with sequential convex optimization and convex collision checking,”The International Journal of Robotics Research, vol. 33, no. 9, pp. 1251–1270, 2014

    work page 2014

  4. [4]

    Hpp: A new software for constrained motion planning,

    J. Mirabel, S. Tonneau, P. Fernbach, A.-K. Sepp ¨al¨a, M. Campana, N. Mansard, and F. Lamiraux, “Hpp: A new software for constrained motion planning,” in2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2016, pp. 383–389

    work page 2016

  5. [5]

    Van Den Bergen,Collision detection in interactive 3D environ- ments

    G. Van Den Bergen,Collision detection in interactive 3D environ- ments. CRC Press, 2003

    work page 2003

  6. [6]

    Mujoco: A physics engine for model-based control,

    E. Todorov, T. Erez, and Y . Tassa, “Mujoco: A physics engine for model-based control,” in2012 IEEE/RSJ international conference on intelligent robots and systems. IEEE, 2012, pp. 5026–5033

    work page 2012

  7. [7]

    Ericson,Real-time collision detection

    C. Ericson,Real-time collision detection. Crc Press, 2004

    work page 2004

  8. [8]

    Approximate convex decompo- sition for 3d meshes with collision-aware concavity and tree search,

    X. Wei, M. Liu, Z. Ling, and H. Su, “Approximate convex decompo- sition for 3d meshes with collision-aware concavity and tree search,” ACM Transactions on Graphics (TOG), vol. 41, no. 4, pp. 1–18, 2022

    work page 2022

  9. [9]

    A fast procedure for computing the distance between complex objects in three space,

    E. Gilbert, D. Johnson, and S. Keerthi, “A fast procedure for computing the distance between complex objects in three space,” inProceedings. 1987 IEEE International Conference on Robotics and Automation, vol. 4. IEEE, 1987, pp. 1883–1889

    work page 1987

  10. [10]

    Enhancing gjk: Computing minimum and penetration distances between convex polyhedra,

    S. Cameron, “Enhancing gjk: Computing minimum and penetration distances between convex polyhedra,” inProceedings of international conference on robotics and automation, vol. 4. IEEE, 1997, pp. 3112–3117

    work page 1997

  11. [11]

    A fast procedure for computing the distance between complex objects in three-dimensional space,

    E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, “A fast procedure for computing the distance between complex objects in three-dimensional space,”IEEE Journal on Robotics and Automation, vol. 4, no. 2, pp. 193–203, 2002

    work page 2002

  12. [12]

    Improving the gjk algorithm for faster and more reliable distance queries between convex objects,

    M. Montanari, N. Petrinic, and E. Barbieri, “Improving the gjk algorithm for faster and more reliable distance queries between convex objects,”ACM Transactions on Graphics (TOG), vol. 36, no. 3, pp. 1–17, 2017

    work page 2017

  13. [13]

    Gjk++: Leveraging acceleration methods for faster collision detection,

    L. Montaut, Q. Le Lidec, V . Petrik, J. Sivic, and J. Carpentier, “Gjk++: Leveraging acceleration methods for faster collision detection,”IEEE Transactions on Robotics, 2024

    work page 2024

  14. [14]

    Proximity queries and penetration depth compu- tation on 3d game objects,

    G. Van Den Bergen, “Proximity queries and penetration depth compu- tation on 3d game objects,” inGame developers conference, vol. 170, 2001, p. 209. 13

    work page 2001

  15. [15]

    Growth distances: New measures for object separation and penetration,

    C. J. Ong and E. G. Gilbert, “Growth distances: New measures for object separation and penetration,”IEEE Transactions on Robotics and Automation, vol. 12, no. 6, pp. 888–903, 1996

    work page 1996

  16. [16]

    A fast n-dimensional ray- shooting algorithm for grasping force optimization,

    Y . Zheng, M. C. Lin, and D. Manocha, “A fast n-dimensional ray- shooting algorithm for grasping force optimization,” in2010 IEEE International Conference on Robotics and Automation, 2010, pp. 1300–1305

    work page 2010

  17. [17]

    Uncertain Pose Estimation during Contact Tasks using Differentiable Contact Features,

    D. Lee, J. Lee, and M. Lee, “Uncertain Pose Estimation during Contact Tasks using Differentiable Contact Features,” inProceedings of Robotics: Science and Systems, Daegu, Republic of Korea, July 2023

    work page 2023

  18. [18]

    A fast growth distance algorithm for incremental motions,

    C.-J. Ong, E. Huang, and S.-M. Hong, “A fast growth distance algorithm for incremental motions,”IEEE Transactions on Robotics and Automation, vol. 16, no. 6, pp. 880–890, 2000

    work page 2000

  19. [19]

    Differentiable collision detection for a set of convex primitives,

    K. Tracy, T. A. Howell, and Z. Manchester, “Differentiable collision detection for a set of convex primitives,” in2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023, pp. 3663–3670

    work page 2023

  20. [20]

    A fast procedure for computing incremental growth distances,

    S.-M. Hong, J.-H. Yeo, and H.-W. Park, “A fast procedure for computing incremental growth distances,”Robotica, vol. 18, no. 4, pp. 429–441, 2000

    work page 2000

  21. [21]

    Ray-shooting algorithms for robotics,

    Y . Zheng and K. Yamane, “Ray-shooting algorithms for robotics,” IEEE Transactions on Automation Science and Engineering, vol. 10, no. 4, pp. 862–874, 2013

    work page 2013

  22. [22]

    Ray casting against general convex objects with application to continuous collision detection,

    G. A. B. Van and D. Bergen, “Ray casting against general convex objects with application to continuous collision detection,” inPlaylogic Game Factory, 2004. [Online]. Available: https: //api.semanticscholar.org/CorpusID:13230913

    work page 2004

  23. [23]

    A numerical solution to the ray-shooting problem and its applications in robotic grasping,

    Y . Zheng and C.-M. Chew, “A numerical solution to the ray-shooting problem and its applications in robotic grasping,” in2009 IEEE International Conference on Robotics and Automation, 2009, pp. 2080–2085

    work page 2009

  24. [24]

    Path connectivity of the free space,

    A. Rodriguez and M. T. Mason, “Path connectivity of the free space,” IEEE Transactions on Robotics, vol. 28, no. 5, pp. 1177–1180, 2012

    work page 2012

  25. [25]

    R. T. Rockafellar,Convex analysis. Princeton university press, 1997, vol. 11

    work page 1997

  26. [26]

    Nemirovski,Introduction to linear optimization

    A. Nemirovski,Introduction to linear optimization. World Scientific, 2024

    work page 2024

  27. [27]

    Eigen v3,

    G. Guennebaud, B. Jacob,et al., “Eigen v3,” http://eigen.tuxfamily.org, 2010

    work page 2010

  28. [28]

    Yale-cmu-berkeley dataset for robotic manipulation research,

    B. Calli, A. Singh, J. Bruce, A. Walsman, K. Konolige, S. Srini- vasa, P. Abbeel, and A. M. Dollar, “Yale-cmu-berkeley dataset for robotic manipulation research,”The International Journal of Robotics Research, vol. 36, no. 3, pp. 261–268, 2017

    work page 2017

  29. [29]

    The quickhull algorithm for convex hulls,

    C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, “The quickhull algorithm for convex hulls,”ACM Transactions on Mathematical Software (TOMS), vol. 22, no. 4, pp. 469–483, 1996

    work page 1996

  30. [30]

    Bullet physics simulation,

    E. Coumans, “Bullet physics simulation,” inACM SIGGRAPH 2015 Courses, ser. SIGGRAPH ’15. New York, NY , USA: Association for Computing Machinery, 2015. [Online]. Available: https://doi.org/10.1145/2776880.2792704

    work page doi:10.1145/2776880.2792704 2015

  31. [31]

    The Open Motion Planning Library,

    I. A. S ¸ucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,”IEEE Robotics & Automation Magazine, vol. 19, no. 4, pp. 72–82, December 2012, https://ompl.kavrakilab.org

    work page 2012

  32. [32]

    MuJoCo Menagerie: A collection of high-quality simulation models for Mu- JoCo,

    K. Zakka, Y . Tassa, and MuJoCo Menagerie Contributors, “MuJoCo Menagerie: A collection of high-quality simulation models for Mu- JoCo,” http://github.com/google-deepmind/mujoco menagerie, 2022

    work page 2022

  33. [33]

    The Pinocchio C++ library – A fast and flexible implementation of rigid body dynamics algorithms and their analytical derivatives,

    J. Carpentier, G. Saurel, G. Buondonno, J. Mirabel, F. Lamiraux, O. Stasse, and N. Mansard, “The Pinocchio C++ library – A fast and flexible implementation of rigid body dynamics algorithms and their analytical derivatives,” inInternational Symposium on System Integration (SII), 2019. 14

    work page 2019