Quote:
Originally Posted by WillAdams
The appropriate cite for ``typography is not a machine solvable problem'' would be the Knuth-Plass paper ``Breaking Paragraphs into Lines'', D.E. Knuth and M.F. Plass, chapter 3 of _Digital Typography_, CSLI Lecture Notes #78.
|
I've not been able to find that paper for free on the net (do you have a link?), but excerpts that I've read from similar papers seem to indicate that there are some ways of defining the problem which are NP-complete, but others that aren't. As I said in another post, it all comes down to what is defined as an acceptable output.
Quote:
Please note that there is no H&J algorithm which can successfully detect and prevent ``stacks'' or rivers --- it seems to be (to use the formal computing term) ``NP Complete'' --- I'd be very interested in any research or algorithm which makes this a solvable problem.
|
Are you sure about that claim? Or is it really that there is no H&J algorithm which can successfully detect and prevent ``stacks'' or rivers that meets somebody's arbitrary criteria for "looks nice"?
Seems to me that simply e.g. detecting and preventing stacks should be fairly straight-forward if you're allowed to arbitrarily add space and break lines wherever you want.
I know that's a pedantic point, but non-computability is a formal thing and needs to be treated formally (i.e. with a better definition of what constitutes a solution before claiming one can't be found).
/JB