The shortest path is usually the wrong one

We keep an interactive computational-geometry tool that turns hand-drawn obstacles into a triangulation, dualizes it into a Voronoi diagram, and searches that diagram for a route. Every primitive is written from scratch, with no geometry libraries, because the point was to understand the pipeline rather than to consume it.

It has been more useful in client conversations than any of us expected, and not for its geometry. It is the clearest illustration we have of a failure that shows up in nearly every operational engagement: the objective everyone states is not the objective anyone wants.

It is the same tool, running here. Draw a few obstacles across the canvas and watch what the planner does with them; the rest of this piece is about why the route it returns is not the short one.

The question people ask, and the one they mean¶

Take a vehicle that has to get from a start point to a goal through a space with obstacles. The reflexive framing is shortest path, and there is a well-known algorithm for that, so the problem looks solved.

The shortest path hugs the obstacles. It grazes every corner, because grazing corners is what minimizing distance means. Ask the person who actually operates the vehicle whether they want that route and the answer is no. What they want is the route that threads the gaps, staying as far from anything solid as the space allows. That is a different objective, and it produces a visibly different path.

Sometimes the structure hands you the answer¶

A Voronoi diagram partitions space by nearest site. Its defining property is that every edge is the locus of points equidistant from its two nearest sites, which means every edge is, by construction, the maximum-clearance corridor between the two obstacles on either side of it. The set of safest routes through the space is not something you search for. It is the diagram.

The construction goes through the dual. Compute a Delaunay triangulation of the obstacle points using Bowyer-Watson incremental insertion, then read the Voronoi diagram straight off it: every triangle’s circumcenter is a Voronoi vertex, and every triangulation edge crosses exactly one Voronoi edge at right angles. Compute one and the other falls out. Edges running to infinity get clipped to the working region with Liang-Barsky, and edges that pass through an obstacle are discarded before the search ever sees them.

The insertion loop is short. The predicate underneath it is where the care goes, and it is the reason a triangulation is a mesh rather than a pile.

const circumcircleContains = (t: Triangle, p: Point) => {  const ax = t.a.x - p.x, ay = t.a.y - p.y;  const bx = t.b.x - p.x, by = t.b.y - p.y;  const cx = t.c.x - p.x, cy = t.c.y - p.y;   const det =    (ax * ax + ay * ay) * (bx * cy - cx * by) -    (bx * bx + by * by) * (ax * cy - cx * ay) +    (cx * cx + cy * cy) * (ax * by - bx * ay);  return det > 0;};

One line changes the objective¶

With a graph whose edges are weighted by clearance, "safest route" becomes a known problem in disguise: find the path that maximizes its minimum edge weight. Dijkstra's algorithm computes the path minimizing a sum of weights. Replace "minimum over sums" with "maximum over minimums" and the same traversal, the same priority selection, the same relaxation loop, computes the widest path instead.

neighbors.forEach((edge) => {  const nextCap = Math.min(cap[u], edge.weight);  if (nextCap > cap[edge.to]) {    cap[edge.to] = nextCap;    parent[edge.to] = u;  }});

That is the part worth carrying to other problems. Teams reach for a different algorithm when the objective changes, and frequently the algorithm is fine and only the accumulation rule needs to change. Recognizing that requires knowing what the algorithm is actually doing rather than which problem it is filed under.

Two things measurement corrected¶

We used a linear scan to select the next node rather than a binary heap, which makes the search quadratic in the node count rather than log-linear. For a graph of a few thousand nodes the constants of the linear scan win outright, and the heap version was measurably slower. Asymptotic complexity is a statement about behavior as the input grows without bound, and a great many production graphs never get near the size where it starts deciding anything.

The second correction was about where the runtime went. Under benchmarking up to roughly twelve thousand eight hundred sites, the cost did not sit where intuition put it. Profiling a pipeline you wrote yourself, on inputs the size you actually have, is worth more than any amount of reasoning about which stage sounds expensive. This is the same lesson our machine learning work produced independently, which is why we now treat it as a rule rather than an anecdote.

Degeneracy is the normal case¶

The entire graph construction rests on one predicate: do these two segments intersect? Written for the general case it is a few lines of cross products. Written for reality it needs explicit branches for every colinear-overlap arrangement, plus a decision about what touching at an endpoint means.

Those branches feel like pedantry until the input contains a wall drawn exactly along an axis, two points at identical coordinates, or three points on a line, at which point they are the whole program. Degenerate input is not an edge case in production data; it is what production data is made of. The same is true of every business rule we have ever implemented, where the awkward case is not rare, it is Tuesday.

The failure mode worth designing for¶

When no safe route exists, the search falls back twice: try the direct line and ship it if nothing blocks it, and otherwise return a single-element path with zero clearance. That second shape lets the interface render "no safe path found" without a special-case branch anywhere in the rendering code.

That is a small decision with a general form. A failure that is expressible in the same type as a success is a failure the rest of the system handles for free. A failure signalled by a null, an exception or a magic value is a failure every caller has to remember. We make this choice constantly in client systems, and it is one of the cheapest things a codebase can be given early.