A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)

In 1988, three engineers came together and developed one of the most clever solutions to the problem of detecting when two complex objects collide. Their solution, the Gilbert Johnson Keerthi (GJK) algorithm, named after the authors, made an incredible impact in the fields of robotics, control, and computer graphics. This video is about understanding this ingenious algorithm from first principles. The video covers a broad range of topics from Minkowski sums and differences to support functions to the full implementation of the 2D GJK algorithm. But what I hope you get out of this is an appreciation of the incredible shifts in perspective that lead to the final algorithm. Coming up with the algorithm is an amazing feat and useful for specific applications, but the overarching problem solving techniques that come through in the journey to the solution is truly invaluable. 0:00 Introducing the Problem 2:02 Convexity 3:15 Infinite Point Perspective 4:07 Minkowski Sums and Differences 6:37 Triangles inside Mink