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

Reply via email to