Where Minkowski Sums Matter

Introduction

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.

Try It: Navigate the Obstacle

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">Drag the <b style="color:#e07b39">orange robot</b> around the canvas. The
<b style="color:#c0392b">red shaded region</b> is the Minkowski sum of the obstacle and the
robot — the set of positions the robot's center must avoid. When the center is outside the
red zone the robot is guaranteed collision-free.</p>
<canvas id="canvas" width="420" height="320"></canvas>
<div class="info" id="info">Drag the 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minkowski sum demo: robot (square) navigating near an obstacle (square).
// The Minkowski sum of obstacle O and robot R (reflected) gives the C-obstacle:
// the set of robot-center positions that cause a collision.
//   For axis-aligned rectangles this is just another rectangle:
//   C-obstacle top-left  = O.top-left  - R.half
// "Collision" iff robot center is inside C-obstacle.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Obstacle: fixed blue square (center, half-width)
const OBS = { cx: 210, cy: 160, hw: 60 };

// Robot: orange square (half-width = 22)
const ROB_HW = 22;
let rob = { cx: 80, cy: 80 };

// C-obstacle (Minkowski sum of obstacle with robot reflected = robot shape):
// For equal axis-aligned squares: C-obs is centered at OBS center,
// half-width = OBS.hw + ROB_HW
const COBS_HW = OBS.hw + ROB_HW;

function inCObs(cx, cy) {
  return Math.abs(cx - OBS.cx) < COBS_HW && Math.abs(cy - OBS.cy) < COBS_HW;
}

function clamp(v, lo, hi) { return Math.max(lo, Math.min(hi, v)); }

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw C-obstacle (Minkowski sum region) — filled red, semi-transparent
  ctx.save();
  ctx.fillStyle = 'rgba(192,57,43,0.18)';
  ctx.strokeStyle = 'rgba(192,57,43,0.55)';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([5, 4]);
  ctx.beginPath();
  ctx.rect(OBS.cx - COBS_HW, OBS.cy - COBS_HW, COBS_HW * 2, COBS_HW * 2);
  ctx.fill();
  ctx.stroke();
  ctx.setLineDash([]);
  ctx.restore();

  // Label for C-obstacle
  ctx.save();
  ctx.font = '11px system-ui, sans-serif';
  ctx.fillStyle = 'rgba(192,57,43,0.85)';
  ctx.fillText('C-obstacle (Minkowski sum)', OBS.cx - COBS_HW + 4, OBS.cy - COBS_HW - 5);
  ctx.restore();

  // Draw obstacle (blue filled square)
  ctx.save();
  ctx.fillStyle = 'rgba(41,128,185,0.22)';
  ctx.strokeStyle = '#2980b9';
  ctx.lineWidth = 2;
  ctx.beginPath();
  ctx.rect(OBS.cx - OBS.hw, OBS.cy - OBS.hw, OBS.hw * 2, OBS.hw * 2);
  ctx.fill();
  ctx.stroke();
  ctx.restore();

  // Obstacle label
  ctx.save();
  ctx.font = 'bold 12px system-ui, sans-serif';
  ctx.fillStyle = '#2980b9';
  ctx.textAlign = 'center';
  ctx.fillText('Obstacle', OBS.cx, OBS.cy + 4);
  ctx.restore();

  // Draw robot (orange square)
  const colliding = inCObs(rob.cx, rob.cy);
  ctx.save();
  ctx.fillStyle = colliding ? 'rgba(231,76,60,0.6)' : 'rgba(224,123,57,0.65)';
  ctx.strokeStyle = colliding ? '#c0392b' : '#e07b39';
  ctx.lineWidth = 2.5;
  ctx.beginPath();
  ctx.rect(rob.cx - ROB_HW, rob.cy - ROB_HW, ROB_HW * 2, ROB_HW * 2);
  ctx.fill();
  ctx.stroke();
  ctx.restore();

  // Robot label
  ctx.save();
  ctx.font = 'bold 11px system-ui, sans-serif';
  ctx.fillStyle = colliding ? '#c0392b' : '#8b4513';
  ctx.textAlign = 'center';
  ctx.fillText('Robot', rob.cx, rob.cy + 4);
  ctx.restore();

  // Center dot on robot
  ctx.save();
  ctx.beginPath();
  ctx.arc(rob.cx, rob.cy, 3, 0, Math.PI * 2);
  ctx.fillStyle = colliding ? '#c0392b' : '#8b4513';
  ctx.fill();
  ctx.restore();

  // Arrow from robot center to C-obs boundary (nearest point) when outside
  if (!colliding) {
    const dx = clamp(rob.cx, OBS.cx - COBS_HW, OBS.cx + COBS_HW) - rob.cx;
    const dy = clamp(rob.cy, OBS.cy - COBS_HW, OBS.cy + COBS_HW) - rob.cy;
    const dist = Math.sqrt(dx * dx + dy * dy);
    ctx.save();
    ctx.strokeStyle = 'rgba(10,125,51,0.5)';
    ctx.lineWidth = 1;
    ctx.setLineDash([3, 3]);
    ctx.beginPath();
    ctx.moveTo(rob.cx, rob.cy);
    ctx.lineTo(rob.cx + dx, rob.cy + dy);
    ctx.stroke();
    ctx.setLineDash([]);
    ctx.restore();

    // Distance label
    ctx.save();
    ctx.font = '10px system-ui, sans-serif';
    ctx.fillStyle = 'rgba(10,125,51,0.8)';
    ctx.fillText(fmt('d=%round%px', { round: Math.round(dist) }), rob.cx + dx / 2 + 4, rob.cy + dy / 2 - 3);
    ctx.restore();
  }

  // Status
  const info = document.getElementById('info');
  if (colliding) {
    info.textContent = '✗ Collision! Robot center is inside the C-obstacle.';
    info.className = 'info collide';
  } else {
    const dx = clamp(rob.cx, OBS.cx - COBS_HW, OBS.cx + COBS_HW) - rob.cx;
    const dy = clamp(rob.cy, OBS.cy - COBS_HW, OBS.cy + COBS_HW) - rob.cy;
    const dist = Math.round(Math.sqrt(dx * dx + dy * dy));
    info.textContent = fmt('✓ Safe — robot center is %dist%px from the C-obstacle boundary.', { dist: dist });
    info.className = 'info safe';
  }
}

// Drag handling (mouse + touch)
let dragging = false;
function getPos(e) {
  const r = canvas.getBoundingClientRect();
  const scaleX = W / r.width, scaleY = H / r.height;
  if (e.touches) {
    return { x: (e.touches[0].clientX - r.left) * scaleX,
             y: (e.touches[0].clientY - r.top)  * scaleY };
  }
  return { x: (e.clientX - r.left) * scaleX, y: (e.clientY - r.top) * scaleY };
}
function onStart(e) {
  const p = getPos(e);
  if (Math.abs(p.x - rob.cx) < ROB_HW + 8 && Math.abs(p.y - rob.cy) < ROB_HW + 8) {
    dragging = true; e.preventDefault();
  }
}
function onMove(e) {
  if (!dragging) return; e.preventDefault();
  const p = getPos(e);
  rob.cx = clamp(p.x, ROB_HW, W - ROB_HW);
  rob.cy = clamp(p.y, ROB_HW, H - ROB_HW);
  draw();
}
function onEnd() { dragging = false; }

canvas.addEventListener('mousedown',  onStart);
canvas.addEventListener('mousemove',  onMove);
canvas.addEventListener('mouseup',    onEnd);
canvas.addEventListener('touchstart', onStart, { passive: false });
canvas.addEventListener('touchmove',  onMove,  { passive: false });
canvas.addEventListener('touchend',   onEnd);

draw();

// Verify (for testing): C-obstacle half-width must equal OBS.hw + ROB_HW
console.assert(COBS_HW === OBS.hw + ROB_HW,
  fmt('C-obstacle size mismatch: expected %hw%%ROB_HW%, got %COBS_HW%', { hw: OBS.hw, ROB_HW: ROB_HW, COBS_HW: COBS_HW }));
// When robot center is exactly at OBS.cx - COBS_HW it is ON the boundary (touching)
const boundaryX = OBS.cx - COBS_HW;
const boundaryCollide = Math.abs(boundaryX - OBS.cx) < COBS_HW; // strict < so boundary = not inside
console.assert(!boundaryCollide, 'Boundary point should NOT be strictly inside C-obstacle');
console.log('Minkowski sum demo: C-obstacle hw =', COBS_HW,
  fmt('= OBS.hw(%hw%) + ROB_HW(%ROB_HW%)', { hw: OBS.hw, ROB_HW: ROB_HW }));

<p class="hint">Drag the <b style="color:#e07b39">orange robot</b> around the canvas. The
<b style="color:#c0392b">red shaded region</b> is the Minkowski sum of the obstacle and the
robot — the set of positions the robot's center must avoid. When the center is outside the
red zone the robot is guaranteed collision-free.</p>
<canvas id="canvas" width="420" height="320"></canvas>
<div class="info" id="info">Drag the 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minkowski sum demo: robot (square) navigating near an obstacle (square).
// The Minkowski sum of obstacle O and robot R (reflected) gives the C-obstacle:
// the set of robot-center positions that cause a collision.
//   For axis-aligned rectangles this is just another rectangle:
//   C-obstacle top-left  = O.top-left  - R.half
// "Collision" iff robot center is inside C-obstacle.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Obstacle: fixed blue square (center, half-width)
const OBS = { cx: 210, cy: 160, hw: 60 };

// Robot: orange square (half-width = 22)
const ROB_HW = 22;
let rob = { cx: 80, cy: 80 };

// C-obstacle (Minkowski sum of obstacle with robot reflected = robot shape):
// For equal axis-aligned squares: C-obs is centered at OBS center,
// half-width = OBS.hw + ROB_HW
const COBS_HW = OBS.hw + ROB_HW;

function inCObs(cx, cy) {
  return Math.abs(cx - OBS.cx) < COBS_HW && Math.abs(cy - OBS.cy) < COBS_HW;
}

function clamp(v, lo, hi) { return Math.max(lo, Math.min(hi, v)); }

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw C-obstacle (Minkowski sum region) — filled red, semi-transparent
  ctx.save();
  ctx.fillStyle = 'rgba(192,57,43,0.18)';
  ctx.strokeStyle = 'rgba(192,57,43,0.55)';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([5, 4]);
  ctx.beginPath();
  ctx.rect(OBS.cx - COBS_HW, OBS.cy - COBS_HW, COBS_HW * 2, COBS_HW * 2);
  ctx.fill();
  ctx.stroke();
  ctx.setLineDash([]);
  ctx.restore();

  // Label for C-obstacle
  ctx.save();
  ctx.font = '11px system-ui, sans-serif';
  ctx.fillStyle = 'rgba(192,57,43,0.85)';
  ctx.fillText('C-obstacle (Minkowski sum)', OBS.cx - COBS_HW + 4, OBS.cy - COBS_HW - 5);
  ctx.restore();

  // Draw obstacle (blue filled square)
  ctx.save();
  ctx.fillStyle = 'rgba(41,128,185,0.22)';
  ctx.strokeStyle = '#2980b9';
  ctx.lineWidth = 2;
  ctx.beginPath();
  ctx.rect(OBS.cx - OBS.hw, OBS.cy - OBS.hw, OBS.hw * 2, OBS.hw * 2);
  ctx.fill();
  ctx.stroke();
  ctx.restore();

  // Obstacle label
  ctx.save();
  ctx.font = 'bold 12px system-ui, sans-serif';
  ctx.fillStyle = '#2980b9';
  ctx.textAlign = 'center';
  ctx.fillText('Obstacle', OBS.cx, OBS.cy + 4);
  ctx.restore();

  // Draw robot (orange square)
  const colliding = inCObs(rob.cx, rob.cy);
  ctx.save();
  ctx.fillStyle = colliding ? 'rgba(231,76,60,0.6)' : 'rgba(224,123,57,0.65)';
  ctx.strokeStyle = colliding ? '#c0392b' : '#e07b39';
  ctx.lineWidth = 2.5;
  ctx.beginPath();
  ctx.rect(rob.cx - ROB_HW, rob.cy - ROB_HW, ROB_HW * 2, ROB_HW * 2);
  ctx.fill();
  ctx.stroke();
  ctx.restore();

  // Robot label
  ctx.save();
  ctx.font = 'bold 11px system-ui, sans-serif';
  ctx.fillStyle = colliding ? '#c0392b' : '#8b4513';
  ctx.textAlign = 'center';
  ctx.fillText('Robot', rob.cx, rob.cy + 4);
  ctx.restore();

  // Center dot on robot
  ctx.save();
  ctx.beginPath();
  ctx.arc(rob.cx, rob.cy, 3, 0, Math.PI * 2);
  ctx.fillStyle = colliding ? '#c0392b' : '#8b4513';
  ctx.fill();
  ctx.restore();

  // Arrow from robot center to C-obs boundary (nearest point) when outside
  if (!colliding) {
    const dx = clamp(rob.cx, OBS.cx - COBS_HW, OBS.cx + COBS_HW) - rob.cx;
    const dy = clamp(rob.cy, OBS.cy - COBS_HW, OBS.cy + COBS_HW) - rob.cy;
    const dist = Math.sqrt(dx * dx + dy * dy);
    ctx.save();
    ctx.strokeStyle = 'rgba(10,125,51,0.5)';
    ctx.lineWidth = 1;
    ctx.setLineDash([3, 3]);
    ctx.beginPath();
    ctx.moveTo(rob.cx, rob.cy);
    ctx.lineTo(rob.cx + dx, rob.cy + dy);
    ctx.stroke();
    ctx.setLineDash([]);
    ctx.restore();

    // Distance label
    ctx.save();
    ctx.font = '10px system-ui, sans-serif';
    ctx.fillStyle = 'rgba(10,125,51,0.8)';
    ctx.fillText(fmt('d=%round%px', { round: Math.round(dist) }), rob.cx + dx / 2 + 4, rob.cy + dy / 2 - 3);
    ctx.restore();
  }

  // Status
  const info = document.getElementById('info');
  if (colliding) {
    info.textContent = '✗ Collision! Robot center is inside the C-obstacle.';
    info.className = 'info collide';
  } else {
    const dx = clamp(rob.cx, OBS.cx - COBS_HW, OBS.cx + COBS_HW) - rob.cx;
    const dy = clamp(rob.cy, OBS.cy - COBS_HW, OBS.cy + COBS_HW) - rob.cy;
    const dist = Math.round(Math.sqrt(dx * dx + dy * dy));
    info.textContent = fmt('✓ Safe — robot center is %dist%px from the C-obstacle boundary.', { dist: dist });
    info.className = 'info safe';
  }
}

// Drag handling (mouse + touch)
let dragging = false;
function getPos(e) {
  const r = canvas.getBoundingClientRect();
  const scaleX = W / r.width, scaleY = H / r.height;
  if (e.touches) {
    return { x: (e.touches[0].clientX - r.left) * scaleX,
             y: (e.touches[0].clientY - r.top)  * scaleY };
  }
  return { x: (e.clientX - r.left) * scaleX, y: (e.clientY - r.top) * scaleY };
}
function onStart(e) {
  const p = getPos(e);
  if (Math.abs(p.x - rob.cx) < ROB_HW + 8 && Math.abs(p.y - rob.cy) < ROB_HW + 8) {
    dragging = true; e.preventDefault();
  }
}
function onMove(e) {
  if (!dragging) return; e.preventDefault();
  const p = getPos(e);
  rob.cx = clamp(p.x, ROB_HW, W - ROB_HW);
  rob.cy = clamp(p.y, ROB_HW, H - ROB_HW);
  draw();
}
function onEnd() { dragging = false; }

canvas.addEventListener('mousedown',  onStart);
canvas.addEventListener('mousemove',  onMove);
canvas.addEventListener('mouseup',    onEnd);
canvas.addEventListener('touchstart', onStart, { passive: false });
canvas.addEventListener('touchmove',  onMove,  { passive: false });
canvas.addEventListener('touchend',   onEnd);

draw();

// Verify (for testing): C-obstacle half-width must equal OBS.hw + ROB_HW
console.assert(COBS_HW === OBS.hw + ROB_HW,
  fmt('C-obstacle size mismatch: expected %hw%%ROB_HW%, got %COBS_HW%', { hw: OBS.hw, ROB_HW: ROB_HW, COBS_HW: COBS_HW }));
// When robot center is exactly at OBS.cx - COBS_HW it is ON the boundary (touching)
const boundaryX = OBS.cx - COBS_HW;
const boundaryCollide = Math.abs(boundaryX - OBS.cx) < COBS_HW; // strict < so boundary = not inside
console.assert(!boundaryCollide, 'Boundary point should NOT be strictly inside C-obstacle');
console.log('Minkowski sum demo: C-obstacle hw =', COBS_HW,
  fmt('= OBS.hw(%hw%) + ROB_HW(%ROB_HW%)', { hw: OBS.hw, ROB_HW: ROB_HW }));

Result

Console

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 Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/minkowski-sum/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Minkowski Sums

Inflate one shape by another — and teach robots where not to go