= Line breaking
\b[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 gives
$$
C_{\rm greedy}=(7-6)^2+(7-2)^2=26,\qquad
\boxed{C_{\rm alternative}=(7-3)^2+(7-5)^2=20.}
$$
An immediately fuller first line can therefore produce a worse paragraph under this particular cost.
\Image[/line-breaking-global-choice.png]
{title=<Greedy line breaking> and a globally optimal choice under squared slack cost}
{description=Original toy example with word widths 3,2,2,5, fixed spaces of width 1 and line width 7. Squared unused-width cost excludes the final line. The generator computes both the greedy grouping and the optimum by <dynamic programming>.}
<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. Then
$$
D(0)=0,\qquad
\boxed{D(j)=\min_{\substack{0\leq i<j\\\ell_{ij}\leq W}}
\bigl(D(i)+c(i,j)\bigr).}
$$
Possible 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.<Breaking paragraphs into lines by Donald E. Knuth and Michael F. Plass>[1981 paper, summary and introduction; paragraph-wide optimization and dynamic programming]{ref}
Back to article page
