Knuth-Plass Thoughts

It's been a while since I wrote this, but I seem to remember that widows are NP-hard at least: fitting them to pages maps onto box-packing.

I really implemented this algorithm so that I could nicely "flow" images in a GUI window. I was working with Sean Parent & Jaakko Järvi on Adam/Eve. My assertion was that there were layout principles (Adam?) for UI similar to the constraint properties for the object model (Eve?). The "other" layout principle was the grid-bag (CSS's box model for grids).

TeX treats the problems of (1) choosing line breaks to turn a stream of words into a stream of lines, and (2) choosing page breaks to turn a stream of lines into a stream of pages, separately; it does #1 and then #2. The Knuth-Plass algorithms addresses #1. I think #2 is done by simpler means; there is some support in it for penalizing widow and orphan lines, but no way for that to feed back to the line-breaking process.

In the common case where your pages are just text with a fixed spacing between lines, the only way for #2 to prevent widows and orphans is to make the page one line taller or shorter, making the margins look weird, which typically also gets penalized, and the only question is which penalty is larger. But if there are any variable spacings on the page, there will be the option of making them slightly larger or smaller in order to push a stray line from one page to another.

There’s a similar problem with paragraphs ending with a very short line. IIRC, nothing special needs to be done about that because the squaring in the formula of the penalty makes the penalty of such a line very high.

If so, nothing special needs to be done about widows and orphans either because TeX first uses essentially the same algorithm to decide where to put page breaks between lines (with page breaks between paragraphs getting lower penalties than page breaks within paragraphs), and having a single line of a paragraph on the top or bottom of a page leads to a fairly high penalty.

Thanks for the interesting replies to my question.

It sounds as though TeX cannot do anything about widows and orphans in the boring "simple" case of a long prose text with a fixed number of lines per page, because the only way[] to improve page breaks in that case would be to change the line breaks, which have already been decided. Mixing up the line-break and page-break stages presumably gives you an NP-hard optimisation problem, and perhaps Knuth was less interested in working on messy heuristic algorithms.

I've just found a couple of references to work in this area:

https://mirrors.mit.edu/CTAN/macros/luatex/generic/lua-widow...

https://onlinelibrary.wiley.com/doi/10.1111/coin.12165

--------

[] I'm assuming that moving the margins or changing the line spacing would be unacceptable because it would make the pages of a book look obviously different from each other. So it turns out that the "simple" case is in some ways harder to handle than the "complex" case in which there are figures and footnotes and so on.

One thought that was proposed back in the 80s was that just as line breaks are considered in the paragraph as a whole, page breaks could be considered in the document as a whole (TeX can’t do this—easily—being Turing complete, in theory it can do anything computable, but the speed would be atrocious). This could be managed by doing things like lengthening or shortening pairs of facing pages by a line or trying to tighten or loosen an individual paragraph to change the number of lines in it. A document formatter which comes at page breaks with the right level of abstraction of the data would be able to manage this with minimal or no human intervention (when I was typesetting Serif magazine with TeX in the 90s, I just went through and fixed page breaks manually which is a typical modern workflow as well).