Comments | pozorvlak: A quick break

pozorvlak

A quick break

Jul 13, 2010 16:39

It occurs to me that not enough people know about TeX's line-breaking algorithm.

Take a paragraph of text; this one, for instance. Form a graph whose vertices are possible line-breaks, and whose edges are the words (and part-words, in the case of hyphenation) between two possible breaks. For instance, if your text is "Fred loves Wilma", then you'd ( Read more... )

computers, programming, tex, beware the geek

Comments 7

stronae July 13 2010, 17:47:14 UTC

Well, it is Knuth, yeah? :)

gareth_rees July 13 2010, 18:50:37 UTC

You might think so, but I believe the paragraph setting algorithm is due to Michael Plass (who also showed that page setting in NP-complete).

necaris July 13 2010, 18:48:41 UTC

Dude. That is absolutely fascinating!

pozorvlak July 14 2010, 12:12:46 UTC

It's clever, isn't it? :-)

figg July 13 2010, 23:30:36 UTC

Aside:The TeX book is awesome.

I don't know why they're still using the local algorithm. Hopefully some TeXpert will pop up in the comments and enlighten me

TeX also doesn't support unicode and a wealth of other features. iirc TeX has only had bugfixes since version 3.0 about 20 years ago.

pozorvlak July 14 2010, 12:13:32 UTC

TeXBook: yes, yes it is.

Do you know if they're upgrading the page-breaking algorithm for XeTeX?

figg July 15 2010, 11:41:29 UTC

Not off the top of my head. I thought that was mostly for unicode & AAT.