Minkowski Sums

Picture a robot arm moving through a factory floor crowded with pillars, boxes and walls. The arm has a physical body — it cannot pass through obstacles. How does a motion planner decide which paths are safe?

The key insight is a shape operation called the Minkowski sum. Given two shapes A and B, their Minkowski sum A ⊕ B is the set of all points you can reach by picking one point from A and one point from B and adding them together. In plain English: slide the center of B over every point in A and take the union of all the positions B can land in.

That sounds abstract. But the payoff is concrete: if the robot's body is shape R and an obstacle is shape O, then the Minkowski sum O ⊕ R is exactly the region the robot's reference point (say, its center) must avoid. The robot's complex shape vanishes — it becomes a point — and the obstacle blooms into a padded forbidden zone.

The idea is named after the German-Lithuanian mathematician Hermann Minkowski (1864–1909), who introduced it in the study of convex bodies and number theory. It was later adopted by computational geometers in the 1980s as the correct tool for robot configuration space planning.

The canvas below shows a square obstacle (blue) and a smaller square robot (orange). The shaded red region is the Minkowski sum of the obstacle and the robot — the set of positions the robot's center must avoid to prevent a collision.

Drag the orange robot around the canvas and notice that it bounces off the forbidden zone, not the bare obstacle edge. The robot is being treated as a single point while the obstacle absorbs the robot's own shape.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="420" height="320"></canvas>
<div class="info" id="info">{{drag_robot}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #f8f9fa; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
canvas { display: block; border: 1.5px solid #cdd; border-radius: 10px;
         background: #fff; cursor: grab; touch-action: none; max-width: 100%; }
canvas:active { cursor: grabbing; }
.info { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; color: #333; }
.safe   { color: #0a7d33; }
.collide{ color: #c0392b; }

// Code not found

Notice that the forbidden zone is always exactly the obstacle inflated by the robot's half-width on every side. When the robot's center is outside the red region, the robot is guaranteed not to touch the obstacle.

The algorithm and its cost depend heavily on the shape of the inputs.

• Convex polygons are the sweet spot. The Minkowski sum of two convex polygons with m and n vertices is also a convex polygon with at most m + n vertices, and it can be computed in $O(m + n)$ time by merging the sorted edge sequences of the two polygons — one of the most elegant linear-time algorithms in computational geometry.
• Non-convex polygons are much harder. The output can have $O(m^{2} n^{2})$ vertices in the worst case, because concave features can interact combinatorially with each other. Computing the exact Minkowski sum of two non-convex polygons with m and n vertices takes O($m^{2}$ $n^{2}$ log(mn)) time with classic algorithms.
• 3-D shapes are harder still. The Minkowski sum of two convex polyhedra can be computed in O((m + n) log(m + n)) time, but for non-convex solids the problem is significantly more complex and the output can be non-manifold.
• Complexity in configuration space: the Minkowski-sum approach reduces robot motion planning to finding a path in the complement of a (possibly very complex) forbidden region. For a single convex robot among convex obstacles this is clean; for a robot with rotating joints among non-convex obstacles it connects to P vs NP — the general motion planning problem for a robot with many degrees of freedom is PSPACE-complete.

The gap between convex and non-convex cases is a recurring theme in computational geometry: a tractable problem for round or convex shapes can explode into intractability the moment concavities appear.

The Minkowski sum is everywhere that shapes must interact:

• Robot motion planning: the configuration-space obstacle (C-obstacle) is the Minkowski sum of the workspace obstacle and the robot's body reflected through the origin. Every major motion planner — from the 1983 Lozano-Pérez algorithm to modern sampling-based planners like RRT — reasons in this space.
• Collision detection in games: modern physics engines (Bullet, PhysX, Box2D) use the GJK algorithm, which implicitly works with the Minkowski difference of two shapes to test whether they overlap. If the Minkowski difference contains the origin, the shapes collide.
• Offset curves in manufacturing: a CNC mill with a round cutter traces the Minkowski sum of the desired cut path with a disk. Shrinking a part inward by a given clearance is the Minkowski sum (or difference) with a ball — an operation called an erosion in mathematical morphology.
• Font and graphic design: the stroke around a path in a vector editor is the Minkowski sum of the path with a small pen shape. Round caps, square caps, and calligraphic shapes correspond to different pen shapes.
• Mathematical morphology: the dilation and erosion operations in image processing are exactly Minkowski sums and differences applied to pixel sets.

Whenever you need to answer "is there any position where this shape fits without touching that shape?" you are, at heart, asking a question about a Minkowski sum. See also convex hull and closest pair for related geometry algorithms.

The Minkowski sum is one of those ideas that look like a curiosity in pure mathematics and turn out to be load-bearing infrastructure in computing. Slide one shape over another, take the union of all positions — and you get a forbidden zone that makes robot navigation, collision detection and manufacturing tolerances all fall out naturally.

For convex shapes the computation is beautifully fast. For non-convex shapes the cost can grow quadratically or worse, a reminder that concavity is where geometric algorithms pay the price. And when a robot has many joints, the configuration space grows exponentially and the planning problem touches the same deep questions raised in P vs NP.

Minkowski sums are a clean example of a mathematical operation that was not invented to solve an engineering problem, yet turned out to be exactly the right tool when the problem eventually arrived.