Connecting Segments: Exit Points

In one line: this is the idea that makes long-distance routing possible, and it is a genuinely elegant one — build a second graph whose vertices are the boundaries between segments, and route on that instead.

The two-level graph

Detailed graph (within a segment)      High-level graph (between segments)
-------------------------------      ----------------------------------
every intersection is a vertex        only EXIT POINTS are vertices
every road is an edge                 edges = precomputed paths between them

       S1        S2                          S4E1 ---- S1E3
   +--------+--------+                        |    \
   |        |        |                        |     \
   |  S4E1  |        |                      S4E2 --- S4E3
   +---S4---+---S5---+
   |  S4E2  S4E3     |                   "the lines connecting exit points
   |        |        |                    are not actually straight — there
   +--------+--------+                    could be many vertices in between"

Exit points act as bridges between neighbouring segments. When calculating routes across multiple segments, we ignore the internal road network of intermediate segments. Instead, we build a high-level graph using only the exit points and the pre-calculated paths between them.

Ignoring the internal roads of intermediate segments is the key move

This is what makes long-distance routing tractable, and it is worth stating plainly.

Driving from Los Angeles to New York passes through thousands of segments. If routing had to consider every road in all of them, you are back to traversing the global graph — which Lesson 2 established is infeasible.

Instead, for a segment you are merely passing through, the only thing that matters is: how do I get from the exit point where I entered to the exit point where I leave, and what does that cost?

That is a single precomputed edge in the high-level graph. Every road inside becomes irrelevant.

So a graph with billions of vertices collapses into one with a few per segment — and the shortest-path algorithm runs on the small one. The detailed graph is consulted only for the source and destination segments, where you genuinely need street-level directions.

This is a hierarchical abstraction, and it is the same instinct as DNS's delegation and task scheduling's internal-versus-external cluster managers: at each level, hide the detail below it and expose only what the level above needs.

The diagram caption is the most important footnote in the chapter

A graph made up of exit points, where the lines connecting the exit points are not actually straight. There could be many vertices in between the two exit points.

An edge in the high-level graph is not a road. It is a summary of an entire precomputed path — potentially hundreds of intersections and turns — collapsed into a single weighted edge.

Two consequences:

The weight is real. It is the precomputed shortest distance and travel time through that segment, not a straight-line approximation. So the high-level shortest path is genuinely optimal, not a heuristic — provided the precomputation is current.

The detail must be recoverable. When you eventually give turn-by-turn directions, you need to expand each high-level edge back into its vertex sequence — which is exactly why Lesson 5 stored "the sequence of vertices along the path" rather than just distance and time.

That storage decision looked like an implementation detail three lessons ago. It is what makes this abstraction usable rather than merely fast.

An edge in the high-level graph is not a road. It is a summary of an entire precomputed path — potentially hundreds of intersections — collapsed to one weighted edge. Two consequences: the weight is real (a precomputed shortest distance, not a straight-line guess), and the detail must be recoverable when you eventually give turn-by-turn directions.

What gets precomputed

Precomputed	Used for
Shortest paths between all exit points of a segment	Traversing a segment you are passing through — the edges of the high-level graph
Paths from exit points to internal vertices	Entering or leaving at the source and destination segments

Two kinds of precomputation for two kinds of segment

The distinction maps onto how a segment participates in a route:

Pass-through segments need only exit-to-exit paths. You enter at one boundary and leave at another; nothing inside matters.

Endpoint segments — where the design or destination lives — need exit-to-internal paths, because you must get from a boundary to an actual address.

That is why both are cached. And it bounds the cost sensibly: exit-to-exit is small (a segment has few exit points), while exit-to-internal is larger but only needed for the segment's own vertices.

Compare Lesson 5's naive all-pairs precomputation, which was O(V²) in the segment's vertex count. Exit-point precomputation is O(E²) where E is the number of exit points — dramatically smaller, since a 5×5-mile square has a handful of boundary crossings and thousands of intersections.

So exit points are not only an abstraction for querying; they are also what keeps the precomputation affordable.

Exit points are a natural bottleneck — and that has a real-world analogue

Because all cross-segment traffic must pass through an exit point, they are structurally load-bearing in a way ordinary vertices are not.

Two consequences worth naming:

Correctness. A segment with few exit points constrains routing — if a bridge or mountain pass is the only crossing, every route through that region uses it. That is genuinely how geography works, and the model captures it correctly rather than as a flaw.

Recomputation cost. When traffic changes on an edge near an exit point, every precomputed path using that exit point becomes stale — which could be a large fraction of the segment's cache. Lesson 11's graph preprocessing service has to handle that, and it is why Lesson 11 distinguishes transitory conditions (do not recompute) from persistent ones (do).

There is also a partitioning implication: segment boundaries should ideally fall where the road network is sparse, so there are few exit points and less recomputation. Drawing a boundary through a dense city centre maximizes exit points and cost. Uniform squares do not respect that — another argument for the non-uniform segments Lesson 12 suggests.

Key takeaway

Exit points turn a global graph into a two-level hierarchy: a detailed graph inside segments and a high-level graph whose vertices are boundary crossings and whose edges are precomputed summaries of entire paths. Passing through a segment costs one edge lookup, so every road inside becomes irrelevant. Precomputing exit-to-exit is O(E²) rather than O(V²), which is what keeps it affordable — and boundaries ideally fall where roads are sparse.

Interview signal by level

Level	What a strong answer sounds like
L4	"Segments connect at their boundaries, so we route between those."
L5	Describes the two-level graph: "exit points become vertices in a higher-level graph whose edges are precomputed paths through segments, so a long route ignores the internal roads of everything it passes through."
Staff+	Notes the precomputation economics and boundary placement: "exit-to-exit precomputation is O(E²) in exit points rather than O(V²) in vertices, which is what makes it affordable — a 5×5 square has a handful of crossings and thousands of intersections. And boundaries should ideally fall where the road network is sparse, so there are fewer exit points and less recomputation when weights change; uniform squares don't respect that. Also worth noting the high-level edges are summaries, so we need the stored vertex sequence to expand them back for turn-by-turn directions."

Next: bounding how many segments to consider.