On 03.03.2005 16:19:24 Victor Mote wrote: > 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 will probably order it anyway because I need it yesterday. :-) That's why I wanted the PDF version which they don't seem to have. Sigh. > 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. I've found other references to discussion about communication between line and page breaking algorithms. But that stuff was mostly overview-style and written in a language I don't understand well: universitary language. That's probably the first time I regret stopping university after one semester because I hate mathematics. :-) > 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". I haven't dared look into the TeX source code, yet, but I've read most of the chapter you mention. Didn't really help because there are many many TeX-specific things in there. > 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. I very much hope so. But it becomes more and more apparent that this will be the greatest challenge in my programmer's life. Wow indeed. Jeremias Maerki
