COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	STAN-CS-80-828
C00004 ENDMK
C⊗;
STAN-CS-80-828
Breaking Paragraphs Into Lines
by Donald E. Knuth and Michael F. Plass (66 pages, November 1980)

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. This algorithm avoids
backtracking by a judicious use of the techniques 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.