KnuthPlass

Knuth–Plass is a line-breaking algorithm designed for high-quality typesetting. Developed by Donald E. Knuth and Michael F. Plass, it finds optimal breakpoints for a paragraph so that the overall appearance of lines is as uniform and aesthetically pleasing as possible within a given line width. The algorithm appeared in their 1981 paper Breaking Paragraphs into Lines and became a core component of the TeX typesetting system.

Mathematically, the algorithm treats line breaking as a global optimization problem. Each potential line end (breakpoint) is assigned a demerit based on the line's 'badness'—a cubic penalty for the amount of leftover space after justification—and any additional penalties for hyphenation, deactivating breaks, or forced breaks. The goal is to select a sequence of breakpoints that minimizes the total demerit across the paragraph. The method uses dynamic programming with a structure called active nodes to keep track of feasible breakpoints, computes optimal subsolutions, and then backtracks to recover the best set of breaks. It also accounts for glue flexibility and penalties that influence justification, producing more even right margins and fewer awkward spaces.

Impact: The Knuth–Plass algorithm has influenced modern digital typography and is implemented in TeX and many TeX-derived systems. It is valued for producing consistent, visually pleasing paragraphs, especially in long texts with varied line lengths and hyphenation opportunities. While more computationally intensive than greedy line breaking, it generally yields better results.