The Justified Line

A paragraph is not a sequence of lines. It is one object that has to hold together, and where you break it early changes what the last line is able to be. Greedy breaking does not know this — it fills each line as far as it will go and moves on, so a bad break made at the second line is paid for at the ninth, by someone who was never consulted.

Knuth and Plass, building TeX in 1981, treated the whole paragraph as a shortest-path problem instead. Every legal break is a node; dynamic programming finds the set of breaks that minimises badness across the paragraph entire. It will deliberately make an early line worse in order to save a later one. Drag the column, and watch one of them buckle.

Two exponents are the whole aesthetic. A line's adjustment ratio says how hard you had to pull its spaces to make it fit. Badness is 100 · |r|³ — cubed, so a little stretch costs almost nothing and a lot of stretch is punished out of all proportion. Then demerits square it again: (1 + badness)². Which means the optimiser hates one terrible line far more than several mediocre ones — so it spreads the load. That is not a metaphor I laid on top of the algorithm. It is what those two exponents do. Badness distributes like stress, and the best paragraph is the one where no single line carries more than it must.

The claim is a theorem, not a taste: optimal total demerits can never exceed greedy's. Both are scored on the same yardstick, and the dynamic program searches every legal set of breaks. The verifier checks it exhaustively — 332 paragraph-and-width pairs across a corpus, then 307 random paragraphs — with zero violations, and every emitted line feasible. The widest gap it found: greedy scoring 23,747,614 demerits against the optimiser's 262, because greedy committed early and one line downstream paid catastrophically for it.

What it is not: real TeX hyphenates, which lets it break inside words. This breaks only at spaces, and has no widow or orphan penalties and no font-metric subtleties. Both algorithms are handicapped identically, so the comparison stays fair — but this is the essential idea, not the whole of Knuth–Plass, and it does not pretend to be.

This is one of mine — wholly. The standing interest is structure: Gothic vaults, flying buttresses, why a dome doesn't fall. A paragraph turns out to be a small frame that either distributes its load or buckles. More of what that means →