[luatex] the hz algorithm

[Reinhard Kotucha]

On 8 August 2010 Martin Schröder wrote:

 > 2010/8/8 Pablo Rodríguez <oinos at web.de>:
 > > I'm not a lawyer, but even in the legal side of this issue (when
 > > the the European doesn't expire until 1/1/2011), there might be a
 > > related patent for a line-breaking algorithm granted to Adobe
 > > (http://www.freepatentsonline.com/6510441.pdf) that might involve
 > > the hz-algorithm (http://typophile.com/node/16525).
 > 
 > That patent should be easy to shoot down as TeX is clearly prior
 > art.  I didn't read it all, but on a cursory glance it looks much
 > like TeX.

The invention is to find optimal line breaks only in a portion of a
paragraph instead of the whole paragraph in order to save resources.
So it's an extension of Knuth's algorithm.

It makes some sense if the cost grows quadratically with the size of a
paragraph and paragraphs are large.  I don't know how much is gained,
but it might be irrelevant since we have computers now which can
compile "The TeXbook" within less than a second.

BTW, you'll find the original of the graph shown in the patent in a
reprint of an article written by Knuth and Plass in

  Donald E Knuth, Digital Typography, CSLI, Stanford 1999, page 107.

The original article is mentioned in the patent.

Regards,
  Reinhard

-- 
----------------------------------------------------------------------------
Reinhard Kotucha			              Phone: +49-511-3373112
Marschnerstr. 25
D-30167 Hannover	                      mailto:reinhard.kotucha at web.de
----------------------------------------------------------------------------
Microsoft isn't the answer. Microsoft is the question, and the answer is NO.
----------------------------------------------------------------------------