"Gluing Boxes and Breaking Lines: Finding Optimal Line Breaks"
Byron Peebles 2003
Abstract
This thesis focuses on the problem of breaking paragraphs into lines; this must be done whether for printing or for screen display. It examines two algorithms for generating the line breaks for a paragraph. A simplistic algorithm of placing words until one does not fit and then moving to the next line is barely acceptable; even so, many commercial word processing and layout programs use this algorithm. The goal of this thesis is to analyze in detail TEX's "total-fit" algorithm that can lead to optimal line breaks given a set of criteria. Furthermore, possible improvements of this algorithm are discussed. A historical look back at typesetting and line breaking is included.