Line breaking

Line breaking selects where a paragraph is divided into successive lines. The choice combines the widths of words and spaces with a measure of acceptable layout. A glyph advance supplies part of the underlying geometry, while the chosen breaks determine which content shares a CSS line box in a web layout.

A greedy algorithm can put as much content as possible on each line before proceeding. Greedy line breaking is easy to compute, but an early choice can leave an awkward short line later. Line breaking with squared slack cost gives a small, explicit example. Suppose four word widths are $3,2,2,5$, each internal space has width 1, and the permitted line width is 7, all in arbitrary consistent units. Greedy grouping produces line lengths $6,2,5$. An alternative grouping produces $3,5,5$. Charging squared unused width on every line except the last givesAn immediately fuller first line can therefore produce a worse paragraph under this particular cost.

Dynamic programming makes the global choice systematic. Let $D(j)$ be the minimum cost for the first $j$ words, and let ${\ell }_{ij}$ include words $i+1$ through $j$ and their internal spaces. For feasible lines, set $c(i,j)=(W-{\ell }_{ij}{)}^2$, except that $c(i,n)=0$ for the final line. ThenPossible break positions form a directed acyclic graph; a feasible line is an edge, so the same calculation finds a shortest path from the start to the end of the paragraph.

Donald E. Knuth and Michael F. Plass developed a richer paragraph-wide method using boxes, adjustable glue and penalties. Their Knuth-Plass line-breaking algorithm accommodates typographic choices beyond the fixed spaces and squared costs in the illustrative model above.^[ref]