Breaking paragraphs into lines

This paper discusses a new approach to the problem of dividing the text of a paragraph into lines of approximately equal length. Instead of simply making decisions one line at a time, the method considers the paragraph as a whole, so that the final appearance of a given line might be influenced by the text on succeeding lines. A system based on three simple primitive concepts called ‘boxes’, ‘glue’, and ‘penalties’ provides the ability to deal satisfactorily with a wide variety of typesetting problems in a unified framework, using a single algorithm that determines optimum breakpoints. The algorithm avoids backtracking by a judicious use of the technique of dynamic programming. Extensive computational experience confirms that the approach is both efficient and effective in producing high-quality output. The paper concludes with a brief history of line-breaking methods, and an appendix presents a simplified algorithm that requires comparatively few resources. [Readers of IAOR will notice that the above abstract has not been included with the usual promptness of this journal. It was brought to the notice of the editor by a reviewer, who remarked that it describes a use of dynamic programming which is employed by hundreds of people every day, the users of TeX and LaTeX. So, with some chagrin that the paper has hitherto been overlooked, it is now included in IAOR. (David Smith, IAOR editor)]