| It's not just line breaking that makes LaTeX beautiful. It's also space placing too. Sometimes you can adjust the distance between letters in a word or distance between words to not break to many lines. The algorithm is similar. The algorithms do find the best breakage but as you can see, there's no need to look for good enough, there's already a nice n log n solution. These algorithms work so well that then you get the problem of rivers. https://en.wikipedia.org/wiki/River_(typography) The reason why efficient DP algorithms exist is because the evaluation function you're trying to minimize is decomposable over the decisions (of where to put a line break). Rivers on the other hand can be optimally evaluated only after you've put your spaces and breaks. Similar issues are encountered in machine learning for sequence tagging or natural language parsing, where the loss function does not always decompose over sequence of decisions. The statistical models used there (that replace Viterbi-like DP algorithm) try to compensate by reinforcement learning or decomposition tricks. It works quite well. |
How efficient is that under local changes? E.g., when the user (or javascript) changes one word in a long paragraph, does the algorithm require a re-analysis of the whole paragraph?