 Knuth-Plass line-breaking algorithm

The Knuth-Plass line-breaking algorithm chooses paragraph breaks using dynamic programming over a representation of the material as typesetting boxes, typesetting glue and typesetting penalties. Boxes supply unbreakable widths; glue supplies normal spacing together with stretch and shrink allowances; penalties express preferences about permitted breaks and can account for a hyphen added when a break is taken.^[ref]

Text justification makes the glue geometry useful. In an illustrative line, suppose box widths total 24 and two glues each have normal width 3 and stretch allowance 2. To fill width 32, the line adjustment ratio isEach glue then becomes $3+r\cdot 2=4$, giving $24+4+4=32$. This example demonstrates proportional stretching; it is one ingredient of paragraph optimization.

The dynamic programming state retains information needed to score later choices. In particular, a line-breaking fitness class records a spacing category, allowing an abrupt change between neighbouring lines to affect the cost. Break position alone would discard that relevant history. The original active nodes include line number and fitness class, with the best accumulated demerits stored as their value.^[ref]

The line breaking with squared slack cost example isolates break selection with fixed word spacing. Here, adjustable typesetting glue and typesetting penalties participate in the paragraph optimization. Donald E. Knuth and Michael F. Plass's 1981 paper documents the method and its development in the TeX project.^[ref]