Shortest Paths Around Obstacles

Imagine a wide floor scattered with square pillars. You stand at one spot and want to reach the door by the shortest walk possible, without passing through any pillar. Which way do you go?

There is a wonderfully physical answer. Tie a string from your start to the goal and pull it taut. It snaps against the corners of the pillars in its way, and what remains is the shortest obstacle-free route. The taut string never curves in open space — it travels in straight segments and only ever bends at a corner of an obstacle.

That single observation is the whole secret. Because the optimal path only turns at corners, we never have to consider the infinitely many points of the floor — just the start, the goal, and the obstacle corners. A continuous geometry problem collapses into a small, finite graph we can search quickly and exactly.

Below is a floor with a few obstacles. Drag the green start and the red goal anywhere on open ground. The route that lights up is the genuine shortest obstacle-free path — built by connecting every pair of mutually visible corners, then running Dijkstra over that visibility graph.

<p class="hint">{{hint}}</p>
<canvas id="floor" width="420" height="320"></canvas>
<div class="status" id="status"></div>
<div class="btns">
  <button id="graph" type="button">{{show_graph}}</button>
  <button id="reset" type="button" class="ghost">{{reset_endpoints}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint .g { color: #0a7d33; }
.hint .r { color: #c92f3c; }
canvas { border: 1px solid #cdd9e3; border-radius: 10px; background: #f4f7fa;
         touch-action: none; display: block; max-width: 100%; cursor: grab; }
canvas.drag { cursor: grabbing; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.on { background: #0a7d33; border-color: #0a7d33; }

// Code not found

Watch how the path behaves. It runs dead straight whenever it can, and bends only at the corners of obstacles — exactly where a real string would catch. Toggle the visibility graph to see every candidate shortcut the algorithm considered; the highlighted route is the cheapest walk through that web of straight lines.

How hard is it to find the shortest path around obstacles? Reassuringly easy — this is a solved problem with an exact polynomial-time algorithm.

• The key theorem. Any shortest path among polygonal obstacles is a sequence of straight segments whose interior turning points are all obstacle vertices. So the optimum lives entirely in the visibility graph: a node for the start, the goal and every corner, with an edge between two nodes whenever the straight segment between them touches no obstacle interior.
• Build it, then search it. With n corners the visibility graph has at most about $n^{2}$ edges; the classic construction (Lee, 1978) builds it in $O(n^{2} \log n)$, later improved to $O(n^{2})$ by Welzl and others. Running Dijkstra on it then returns the exact shortest path.
• Total cost. The whole pipeline is comfortably polynomial — roughly $O(n^{2} \log n)$ — and gives the provably optimal route, not an approximation.
• Not every "shortest path" is this kind. Restrict turns to a grid, add costs and time, or move to three dimensions among polyhedra, and the picture changes — the 3D version becomes NP-hard (Canny & Reif, 1987).

The contrast worth keeping is with its famous relative, the Traveling Salesman / route problem. Finding the best order to visit many stops is NP-hard; finding the shortest way between two points around obstacles is squarely in P. Geometry, not just graphs, is what makes this one tractable.

"Get from here to there without bumping into things" is one of the most common tasks in the physical and digital world, and the visibility graph is its workhorse:

• Robot motion planning: a robot reduced to a point navigates a workspace of obstacles by exactly this construction — one of the founding ideas of motion planning.
• Video-game navigation: characters route around walls and scenery using visibility graphs or their close cousins (navmeshes), producing those natural corner-hugging paths.
• Geographic routing: planning a ship's or drone's course around no-go zones is a shortest-path-with-obstacles problem on a map.
• Chip layout (VLSI): wiring a connection across a board while dodging blocked regions is the same geometric question at microscopic scale.

Learn why the taut string only bends at corners and you have met computational geometry's friendliest result — a continuous problem made finite, then solved exactly with a graph search.

The shortest path around obstacles hides an elegant truth: the answer only ever bends at corners, so the whole continuous floor collapses into a finite visibility graph we can search exactly. No guessing, no approximation — just a string pulled taut and a polynomial-time algorithm that matches it.

It is a refreshing counterpoint to the intractable problems nearby. Visiting many stops in the best order is the NP-hard route problem, and even telling a short path from a long one can hide surprises. But getting from A to B around walls? That one we have fully, provably solved.