Let's say I have a convex obstacle given by the vertices in their convex hull. Specifically, the obstacle is given by points {(1,0), (2,0), (2,2)}. In addition, I have a robot which is just a unit square, so we could represent it with coordinates {(0,0), (1,0), (1,1), (0,1)}.
Now what I want is to get the convex hull of a new obstacle that has been expanded from all sides by 1 such that any point inside the convex hull would be infeasible and I can quickly tell that it's not a legal position of the robot.
I've been told that we can use the Minkowski sum to solve this problem, I don't see it. If I take the Minkowski sum of my two sets, I get
{(1,0), (2,0), (2,1), (1,1), (2,0), (3,0), (3,1), (2,1), (2,2), (3,2), (3,3), (2,3)}
This isn't convex, but we could easily remove the internal points. But despite this, it seems I've only expanded the right side of this obstacle not all sides. I could potentially also potentially use the unit squares in all quadrants of the euclidean space, but will this always work? How do I know that the convex hull of the Minkowski sum with 4 unit squares indeed defines the illegal configuration space?
I'm not sure if this is what you are looking for:
Suppose $C$ represents the convex obstacle and $R$ represents the robot floorplan if the robot is located at the origin.
If you move the robot to $x$ then the robot flooorplan is $\{x\}+R$.
Then the robot flooorplan intersects the obstance iff $\{x\}+R$ intersects $C$ iff $x \in C-R$ (the Minkowski difference).
It doesn't really change anything, but if the robot is symmetric about the origin then $R=-R$ (as a set) and so $C-R = C+R$.
Note that if $R$ is the convex hull of $r$ points and $C$ is the convex hull of $c$ points then $C-R$ is the convex hull of $c \cdot r$ points.