Jeremias Maerki wrote: > While looking for material on page breaking I found several > references to this document: > > http://wwwlib.umi.com/dissertations/fullcit/8124134 > > Does anyone know if it's worth ordering and waiting for it? > The unfortunate thing is that they don't seem to have a PDF > version that I could download immediately for a reasonable fee.
Wow. This looks like it is very valuable. I have ordered it for my own use, and I'll be glad to give you a "book review" when it arrives to help you decide whether it is worthwhile for you or not. I am especially interested in the summary's comment: "For certain simple badness functions, the pagination problem is NP-complete;" Dealing with that challenge is the likely tricky spot in all of this. My intuition has always been that the page-breaking problem is much more complicated than the line-breaking one, partly because lines must be laid out to even think about page-breaking (and line lengths can change as they move around), partly because you are effectively working with changes in two dimensions instead of one, and partly because there seem to me to be a lot more variables in the problem. I am hoping to find some insight into the detection and workarounds for the NP-complete situations. Note that Stanford is Knuth's school, the date year is the same as that of Chapter 3 of Knuth's Digital Typography, and that the author is the co-author of that article. It may be possible to infer the same information from looking at the TeX source code. Also, another source of similar information would be Volume I of Knuth's "Computers and Typesetting", aka "The TeXbook". It is essentially a commentary on TeX, by Knuth. Chapter 15 is entitled "How TeX Makes Lines into Pages". You guys are way ahead of me in terms of thinking about how to implement this stuff. As you know, my approach has been to leave this stuff for last, preferring instead to solve the outer-layer problems first, and provide for multiple implementations that can be improved in parallel. However, I have a great interest in your efforts, and will be glad to help any way that I can. And, FWIW, I think you are on the right general track, in this regard at least. Victor Mote