sandbox · exhibit 0006

Where the lines end

Your browser sets a paragraph the way you would pack a suitcase in a hurry: one line at a time, keeping whatever fits, never reopening a line it has closed. TeX reads the whole paragraph before it commits to anything, and pays for a cramped line here to buy a comfortable one four lines later. Both run below, on the same words, in the same font, at the same measure.

First fit — one line at a time

Optimal — the whole paragraph at once

tight decent loose very loose overfull bar length = how far the spaces moved

Check it

The claim on this page is not that the second setting looks nicer. It is that the second setting is the best arrangement of these words at this measure — that no other set of line breaks scores lower. That is a claim with a finite number of counterexamples, so the button tries all of them: for a short paragraph it enumerates every subset of the legal break points, scores each one with arithmetic that shares no line with the search, and looks for anything cheaper. Then it asks the browser where the words actually landed, which is a different question again.

A paragraph is a row of rigid boxes — words — separated by glue, which has a natural width and knows how far it will stretch and how far it will squash. Breaking a line means choosing which pieces of glue become the ends of lines. Every other piece must then absorb the difference between what the line naturally is and what the measure demands. The adjustment ratio is how much of its stated stretch or shrink a line asks of its glue: 0 is the width the spaces wanted, +1 is every space pulled to its stated limit, −1 is every space squashed to its limit. Cubing it gives badness, so being slightly off costs almost nothing and being far off costs everything.

That much is one line's problem. The paragraph's problem is that the lines are not independent: where this line ends decides where the next one can. First fit answers it greedily and can be beaten. The optimal answer is a shortest path — every legal break is a node, every possible line is an edge, and its length is that line's badness squared, plus a fee for hyphenating twice in a row, plus a fee for a tight line sitting next to a very loose one. Knuth and Plass published it in 1981; what you scroll past in a book is the arithmetic below.

0006 · no fetch, no font file, no library the entry