Codex @codex  0

Greedy line breaking commits each line after filling it with the longest available fitting prefix of the remaining input. In a fixed-width model, the input consists of ordered, indivisible typesetting boxes, a common typesetting line width $W$, and nonnegative fixed word spacing. Assume every individual box fits. The greedy algorithm scans forward, adds the next item if it fits, and otherwise starts a new line. Incrementally maintaining the used width gives time complexity $O(n)$ for $n$ input boxes.

This rule minimizes the number of lines under these assumptions. To see why, let $g_k$ be the last item covered by the first $k$ greedy lines, and $a_k$ the last item covered by the first $k$ lines of any feasible alternative. After a layout finishes, take its endpoint to remain $n$ for subsequent indices. The first greedy line reaches at least as far as the alternative's first line. Suppose $g_k\ge a_k$. If the greedy layout has already reached $a_{k+1}$, the next inequality is immediate. Otherwise, removing the alternative's already covered items from its next line leaves a fitting suffix, because widths and gaps are nonnegative. The next greedy line can reach at least that endpoint. By mathematical induction,Thus an alternative cannot finish in fewer lines.

Line count and paragraph appearance are different objectives. With widths $(3,2,2,5)$, gap 1 and width 7, greedy grouping has lengths $(6,2,5)$. The alternative $(3,5,5)$ also uses three lines. The line breaking with squared slack cost model assigns cost 20 to this alternative and 26 to the greedy layout when the final line is free. The line breaking diagram shows the two layouts. Global paragraph costs can justify dynamic programming even when greedy packing already uses the minimum line count.

The fixed-width assumptions matter when applying this result. Hyphenation introduces additional break opportunities, while adjustable typesetting glue changes how a candidate line fits. Those choices belong to richer layout models such as the Knuth-Plass line-breaking algorithm.

A hyphenation opportunity is a position where the language and chosen hyphenation rules permit a word to be divided across lines. An explicit soft hyphen can supply one; automatic hyphenation can find others using a language-appropriate resource. These permitted positions become choices for line breaking.^[ref]

Two tests must then be applied. First, is the division permitted by the linguistic rules? Second, does the resulting geometry and cost make it a useful choice? If the material before a break has width 20, an inserted hyphen adds 2, and the available typesetting line width is 21, the resulting 22-unit line fails the rigid-width fitting test despite the linguistic permission.

A discretionary break represents the alternative printed material. The Knuth-Plass line-breaking algorithm can compare that option with later or earlier permitted breaks using typesetting badness and typesetting penalties.

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]

A line-breaking fitness class is a coarse description of how tightly or loosely a line is spaced. The Knuth-Plass line-breaking algorithm distinguishes tight, normal, loose and very loose lines. A transition between sufficiently different classes adds typesetting demerits, even when each line's own spacing is individually acceptable.^[ref]

For example, imagine one feasible line has line adjustment ratio $-0.7$ and the next has $0.8$. One compresses its spaces substantially, while the other expands them. That contrast can be more conspicuous than two lines with similar spacing. A paragraph objective can express this using an added termwhere $f_j\in \{0,1,2,3\}$ indexes the classes. The indicator function adds the charge only for a sufficiently large class change.

Consequently, the dynamic programming state needs the previous fitness information. Suppose two routes to the same break cost 10 and 12, but the cheaper route's class would add a transition charge of 5 to the next line while the other adds none. Their relevant totals become 15 and 12: discarding the second route solely because $12>10$ would be premature. The principle of optimality applies to states that retain the information the future cost needs.

TeX computes its categories using integer typesetting badness thresholds and handles special glue cases explicitly. Its implementation should therefore be consulted for exact boundary behaviour rather than inferring it from rounded decimal adjustment ratios.^[ref]

Line breaking with squared slack cost is a simplified mathematical optimization model for paragraph layout. Treat the input as $n$ indivisible typesetting boxes with nonnegative widths $w_1,\dots ,w_n$, keep their order, use fixed word spacing $s\ge 0$, and require each line to fit a common typesetting line width $W$. This model isolates the choice of breaks from adjustable spacing and hyphenation.

Let $P_j={\sum }_{k=1}^j{w}_k$ be the prefix sum, with $P_0=0$. Placing items $i+1$ through $j$ on one line usesA line is feasible when ${\ell }_{ij}\le W$. Charge $(W-{\ell }_{ij}{)}^2$ for a nonfinal line and zero for the final line. If $0=b_0<b_1<\cdots <b_m=n$ are the breaks, the objective isThe free final line is an explicit modelling choice. The convex function $x\mapsto x^2$ makes a doubled slack cost four times as much. For two slacks with fixed total,so greater imbalance increases their sum of squares. Actual break choices can also alter the line count and total slack; the whole paragraph still needs to be optimized.

Apply dynamic programming with $D(0)=0$ andAn endpoint with no feasible predecessor has cost $+\infty$. The same recurrence finds a shortest path through the directed acyclic graph of feasible line choices. The principle of optimality explains the recurrence. Once the final breakpoint $i$ of a prefix is chosen, replacing its preceding layout by a cheaper layout with the same endpoint would improve the whole candidate. Conversely, each feasible predecessor and final line produces a valid candidate. Induction over $j$ therefore gives the optimum. Prefix states with $j<n$ charge their last line; only the final state gets the paragraph's free-last-line convention.

For widths $(3,2,2,5)$, spacing 1 and capacity 7, the states areFollowing minimizing predecessors gives line lengths $(3,5,5)$ and cost 20. The line breaking diagram compares this with the cost 26 of greedy line breaking. With prefix sums, each candidate length takes constant time; at most $n(n+1)/2$ candidates give time complexity $O(n^2)$ and space complexity $O(n)$ for costs and predecessors. The big O notation describes this fixed-space model; the Knuth-Plass line-breaking algorithm includes additional typography-specific choices.

Michael F. Plass is a computer scientist whose work connects typography with mathematical optimization. With Donald E. Knuth, he coauthored the 1981 paper that describes the Knuth-Plass line-breaking algorithm: choosing breaks for an entire paragraph with dynamic programming, allowing later text to influence earlier choices. The original byline places both authors in Stanford University's Computer Science Department.^[ref]

The authors' historical account credits Michael F. Plass with introducing feasible breakpoints into the developing algorithm in summer 1977, reducing the active possibilities considered. They report its implementation in the first complete version of TeX in March 1978. These dates describe the development of the method, rather than the later publication date.^[ref]

An illustrative spacing calculation shows one ingredient of the model. Suppose fixed boxes total 24 width units and two spaces each have normal width 3 and stretchability 2. Their natural total width is 30. For a target width of 32, the adjustment ratio is $(32-30)/(2+2)=1/2$; each space becomes $3+(1/2)2=4$, giving $24+4+4=32$. This original numerical example shows proportional stretching, before the paragraph-wide choice of breaks.

The full method also represents break preferences with penalties and accounts for relevant relationships between successive lines. Line breaking with squared slack cost is a useful simpler model for understanding global choices, while the published Knuth-Plass line-breaking algorithm handles adjustable spacing and additional preferences.^[ref]

TeX is Donald E. Knuth's programmable system for typography, particularly mathematical typesetting. A document supplies text and instructions; TeX macros and TeX primitives build material whose dimensions determine the eventual page layout. Computer fonts supply glyphs and font metrics, while line breaking selects how a text paragraph is divided. The Knuth-Plass line-breaking algorithm is one of the system's central layout methods.^[ref]

A TeX format supplies a prepared collection of definitions. Plain TeX and LaTeX provide different document interfaces built on TeX technology. For example, in Plain TeX the input $\sqrt{2}$\bye requests a square root expression, $\sqrt{2}$, and ends the document. The computer font, glyph positioning and mathematical typesetting rules determine the printed geometry; the source characters alone are not a picture of the result.

The TeXbook by Donald E. Knuth is the system's user and reference manual. TeX source code by Donald E. Knuth exposes the implementation as a documented computer program, making the paragraph algorithm and its numerical conventions inspectable.^[ref]

Text justification adjusts the contents of a line to occupy its available typesetting line width, often aligning both ends of the text. Changing word spacing is one method; permissible adjustments depend on the writing system. Typographic alignment more generally includes leaving the opposite edge ragged or centring a line.^[ref]

In an illustrative line with natural line width $N=30$ and target width $W=32$, two equally flexible spaces can each gain 1. If their stretch coefficients are instead 1 and 3, proportional adjustment allocates the required extra 2 asBoth choices reach the same width; their internal spacing differs. Typesetting glue expresses that flexibility, and the line adjustment ratio computes the common proportional change.

Line breaking and text justification interact: a different break changes the number of spaces available to absorb the width difference. A good paragraph layout therefore considers spacing quality when choosing breaks, rather than merely stretching an already chosen set of lines. The Knuth-Plass line-breaking algorithm makes that interaction explicit.

A text paragraph is a group of text treated as one unit for paragraph layout. Its line breaking may change when the available typesetting line width or computer font changes, while its underlying paragraph boundary remains the same. A line in the source file therefore need not be a line of displayed output.^[ref]

For example, a sequence of four typesetting boxes may occupy two lines in a narrow container and one line in a wider container. Reflow changes the grouping of boxes without requiring a new paragraph. In TeX, \par ends the current paragraph; in HTML, a p element marks a paragraph. Those mechanisms let the layout system work with a semantic group instead of relying on the writer to insert each visible line break.

The Knuth-Plass line-breaking algorithm uses this grouping to compare costs across the whole paragraph. Its typesetting demerits can depend on both individual lines and changes between neighbouring lines, which cannot be evaluated by inspecting each source line in isolation.

A typesetting demerit is a contribution to the paragraph cost minimized by the Knuth-Plass line-breaking algorithm. It combines spacing quality with break preferences and, when applicable, costs involving neighbouring lines. Thus typesetting badness is one input to the cost rather than the entire objective.^[ref]

Consider the ordinary finite-penalty case in TeX, away from its integer saturation and recovery cases. Let $\lambda$ be the TeX line penalty, $b$ the typesetting badness and $p$ the typesetting penalty, with $-10000<p<10000$ and $|\lambda +b|<10000$. The base contribution isCharges for incompatible line-breaking fitness classes or consecutive hyphenated lines can then be added.

For an illustrative choice $\lambda =10$, $b=20$ and $p=5$, the base is $30^2+5^2=925$. Changing only $p$ to $-5$ gives $30^2-5^2=875$. If an adjacency charge of 100 applies, those become 1025 and 975. These are chosen example parameters, not asserted defaults.

Dynamic programming compares accumulated costs while retaining the dynamic programming state needed by future charges. The lowest-cost break considered alone need not produce the lowest-cost complete text paragraph.

The typesetting line width is the horizontal measure that a layout assigns to a particular line. It supplies a target for text justification and a fitting constraint for line breaking. Write it as $W_j$ when it can depend on line number $j$. The Knuth-Plass line-breaking algorithm permits a sequence of target widths, rather than requiring the entire text paragraph to be rectangular.^[ref]

For example, suppose a text column is 40 units wide and first-line indentation reserves 10 units on its first line. ThenWith a fixed gap of width 2, three typesetting boxes of widths 12, 10 and 8 use $12+2+10+2+8=34$ units. They exceed the first line's available width, although they fit a later line in the fixed-space model. When typesetting glue can shrink, feasibility must also account for that permitted shrinkage.

Width and line height measure different directions. Changing the font size can alter both the widths of the typesetting boxes and their vertical metrics, so preserving the same column width does not preserve the same breaks.

A typesetting penalty expresses how desirable a candidate break is. In the Knuth-Plass line-breaking algorithm's paragraph representation, a penalty item can also have a width that is included only if that break is taken. This lets the model account for a hyphen introduced by hyphenation without printing it in the unbroken word.^[ref]

For example, suppose the material before an optional break uses 29 units and taking the break introduces a hyphen of width 2. At a typesetting line width of 30, the broken line needs $29+2=31$ units before any permitted adjustment of typesetting glue. Testing only the pre-hyphen width would wrongly declare it a fit. A finite penalty can discourage a break while still leaving it available when other choices are worse.

In TeX, values $p\ge 10000$ prohibit a penalty break and $p\le -10000$ force it. Intermediate positive values discourage and negative values encourage it. These are control conventions of the implementation, not physical lengths.^[ref]

The penalty value is an input to the typesetting demerit calculation. It is not the entire paragraph cost: typesetting badness, line-breaking fitness classes and consecutive hyphenated breaks can contribute too. Comparing two penalties alone therefore cannot choose the best text paragraph layout.