# Collision Detection Accelerated: An Optimization Perspective

**Authors:** Louis Montaut, Quentin Le Lidec, Vladimir Petrik, Josef Sivic, Justin Carpentier  
**arXiv:** [2205.09663](https://arxiv.org/abs/2205.09663)  
**Date:** 2022-05-19  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2205.09663v2/

## Key points

- Detection of collisions between two convex shapes is crucial for physics engines and robot motion planners.
- Traditionally, this problem has been approached as a computational geometry problem using the GJK algorithm.
- In this work, collision detection is viewed as a convex optimization problem.
- The authors establish that the GJK algorithm is a specific sub-case of the Frank-Wolfe (FW) algorithm in convex optimization.
- They introduce a new collision detection algorithm that significantly reduces the number of iterations required to solve collision detection problems compared to the state-of-the-art GJK algorithm.
- The proposed accelerated collision detection method was benchmarked on two datasets composed of strictly convex and non-strictly convex shapes, showing up to two times faster computation times than the GJK algorithm.
- This improvement in speed is attributed to their use of an optimization-based approach that leverages recent advances in Nesterov acceleration and Frank-Wolfe methods.
- This work provides a new perspective on collision detection and offers an alternative approach that can potentially improve performance for various applications such as robotics, gaming engines, and virtual reality simulations.

## Summary

The detection of collisions between two convex shapes is a crucial aspect of any physics engine or robot motion planner. Traditionally, this problem has been approached as a computational geometry problem, with the Gilbert, Johnson and Keerthi (GJK) algorithm being the most commonly used approach today. However, in this work by Louis Montaut et al., collision detection is viewed as a convex optimization problem. The authors establish that the GJK algorithm is a specific sub-case of the Frank-Wolfe (FW) algorithm in convex optimization. By adapting recent works linking Nesterov acceleration and Frank-Wolfe methods, they introduce a new collision detection algorithm that significantly reduces the number of iterations required to solve collision detection problems compared to the state-of-the-art GJK algorithm. The proposed accelerated collision detection method was benchmarked on two datasets composed of strictly convex and non-strictly convex shapes. The results show that their approach leads to up to two times faster computation times than the GJK algorithm. This improvement in speed is attributed to their use of an optimization-based approach that leverages recent advances in Nesterov acceleration and Frank-Wolfe methods. This work provides a new perspective on collision detection and offers an alternative approach that can potentially improve performance for various applications such as robotics, gaming engines, and virtual reality simulations. Overall, this study highlights the importance of considering different perspectives when tackling complex problems like collision detection and demonstrates how insights from one field can be applied to another field for significant improvements in performance.