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

Reply via email to