What, Why, How of Convex Hulls in robotic collision detection

One essential and crucial concept in today’s Computation geometry is Convex Hull. As it finds applications that are spread out diverse in various domains of engineering and sciences the research scope for optimizing its algorithms continues even today. Though a large part of the problem is solved researchers believe there is a large scope for it in translational research and pure mathematics.

Convex hulls find their application in collision detection and avoidance, Shape analysis, smallest enclosing box, etc.

To answer the question of “WHAT IS A CONVEX HULL?” and intuitively understand the Convex hull in simple terms, I would like to quote Joseph O’Rourke’s explanation of the convex hull

The convex hull of a set of points in a plane (2-dimension) is the shape taken by a rubber band stretched around nails pounded onto the plane at each point. The boundary of the convex hulls of points in 3 dimension is the shape taken by plastic wrap stretched tightly around the points.

This is what a convex hull (i.e., green boundary) of 350 points would look like.,

To answer the question of “Why convex hulls” are used in robotic collision detection. Imagine a turtle bot on a 2D plane that tries to navigate from point A to point B on 2D space. The easiest…