3 ms·
Minimizing Minkowski difference between convex bodies can also be formalized as a quadratic program. I wonder how the GJK performs against the QP formulation.
by markisus 3y ago
Minimizing Minkowski difference between convex bodies can also be formalized as a quadratic program. I wonder how the GJK performs against the QP formulation.
- lqr 3y agoHere is a recent and interesting paper connecting GJK and convex optimization [1]. They show that GJK is equivalent to the iterations of the Frank-Wolfe algorithm applied to the QP, and that recent improvements to Frank-Wolfe can be applied to improve GJK. Frank-Wolfe is a somewhat less well-known (compared to simplex, interior point, etc) convex optimization algorithm with many interesting properties [2, Section 3.3]. [1] https://roboticsproceedings.org/rss18/p039.html https://roboticsproceedings.org/rss18/p039.html [2] https://arxiv.org/abs/1405.4980 https://arxiv.org/abs/1405.4980