51

I have only basic knowledge of the TeX internals, so I hope what I am saying here is not complete nonsense. If I understand correctly, in TeX, horizontal positioning / line breaking is done using a rather advanced algorithm based on a paragraph-level optimization (Knuth-Plass); it allows for concepts such as glue and line break penalties, and gives considerably better results than the more naive approach of, say, MS Word.

On the other hand, I seem to understand that nothing similar is used for vertical positioning of text. Lines are shipped out as soon as they are done and pages are filled using the obvious greedy algorithm. Widows and orphans are handled using special tricks.
[EDIT: this is not entirely correct, see Hendrik Vogt's answer below --- there is an optimization algorithm involved, although it's only local optimization over a single page and not KP]

So, a question arises naturally to me:

why isn't something similar to Knuth-Plass used also for page breaks and the vertical layout of text? Are there major complications?

|improve this question
  • 2
    The interline spaces do not offer the flexibility of kerning or horizontal spacing freedom. It becomes very ugly quickly so I think(!) it's not worth the effort. And also the pages are shipped out immediately whenever they are processed for old technology. My guess is that it's not efficient (for the time when the tools are created) – percusse May 14 '13 at 19:14
  • 1
    AFAIU, when TeX was created, just keeping a full page in memory was already a significant resource strain. And a simplistic algorithm "cut the page at the next convenient point" isn't too bad, as you at most see the even/odd pages at a time. – vonbrand May 14 '13 at 20:40
40

this was addressed by Knuth in a q&a session in st. petersburg, florida, published in tugboat: - TUG'95: Questions and Answers with Prof. Donald E. Knuth, pp.18 (bottom of column 2) - 20; the session was republished in Digital Typography, with the relevant question starting on p.594.

the page-breaking problem was also the subject of Michael Plass' dissertation, Optimal Pagination Techniques for Automatic Typesetting Systems, posted on the tug web site.

|improve this answer
25

It was proved by Plass, that the page breaking problem can be NP-complete. Computers were about 10^4 times slower than nowadays, so it was a problem.

|improve this answer
  • 3
    Floats are the biggest problem, I believe. One could conceive much more complicated paragraphing algorithms where rivers, insertions (flowing around figures) or dynamic computation of line width to accommodate columns with different width (thus interacting with the output routine) that would probably suffer of the same problem. – egreg May 14 '13 at 20:16
  • 1
    From these answers I gather that it was a problem, given the computing limitations at the time. But has anybody tried to implement something like this now? Would it be feasible? – Juan A. Navarro May 22 '13 at 8:11
  • 1
    @JuanA.Navarro I know that Marek Ryćko tries to implement such a feature, but I don't know how advanced is his work. – Przemysław Scherwentke May 22 '13 at 11:17
  • 3
    Hmm, I think it was the computer memory rather than the speed that was relevant. See also the first link in barbara's answer. – Hendrik Vogt May 22 '13 at 14:19
  • 3
    @JuanA.Navarro The issue was addressed by the author of Patoline. I'm not entirely sure what was his approach. I believe that he tries to fit in the paragraphs, and if he fails to do it reasonably well, he unsets the previous page, re-break the paragraphs and gives it another try. However, I'm afraid that once you sub-optimize an NP-complete problem, you get seriously unstable results (much more unstable than what happens with TeX). – yo' Jun 4 '14 at 8:14
22

Your assumption isn't quite correct, TeX doesn't simply use a greedy algorithm to fill pages. Each page break is chosen in such a way that at this point it is optimal. In order to achieve this, TeX actually typesets more material than would fit on the page and then chooses the break with the smallest badness. For example, if there's some vertical space that can be stretched or shrunk, then widows and orphans can be avoided in most cases. Or TeX uses the available shrink to fit not only a section header but also the first two lines of the corresponding section onto the current page.

What TeX does not do is optimizing over the whole set of page breaks. So it can happen that the first page break is just great, but only at the price of the second one being lousy; TeX doesn't look as far ahead as the next page break. The main reason for this seems to be memory constraints of the computers at the time TeX was designed. From the TeXbook, page 110:

TeX breaks lists of lines into pages by computing badness ratings and penalties, more or less as it does when breaking paragraphs into lines. But pages are made up one at a time and removed from TeX’s memory; there is no looking ahead to see how one page break will affect the next one. In other words, TeX uses a special method to find the optimum breakpoints for the lines in an entire paragraph, but it doesn’t attempt to find the optimum breakpoints for the pages in an entire document. The computer doesn’t have enough high-speed memory capacity to remember the contents of several pages, so TeX simply chooses each page break as best it can, by a process of “local” rather than “global” optimization.

It appears that the typesetting system Lout does some optimization of page breaks over several pages:

Lout uses Knuth's (the author of TeX, on which LaTeX is based) optimal line breaking algorithm, and has extended it to paragraph breaking across pages.

|improve this answer
1

I wrote a typesetting system that uses Knuth-Plass for both horizontal and vertical mode. Using it for vertical mode made some things more complex than they would have been otherwise. (For example, a page break to an odd page, switching number of columns, or positioning footnotes.) But I was able to specify things like "Try to put images on the same spread as the image reference". Also I was able to avoid breaking footnotes altogether. These things are really only possible later in a chapter, so it's of limited use.

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.