= Greedy line breaking
\b[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 \b[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\geq 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>,
$$
\boxed{g_k\geq a_k\quad\text{for every }k.}
$$
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>.
Back to article page
