Optimizing Paragraph Line Breaking with Lexical Alternatives

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Optimizing Paragraph Line Breaking with Lexical Alternatives"

by

FUNG Wai Chuen

Abstract:

This thesis studies paragraph line breaking under lexical variation. We 
consider paragraphs in which selected sites admit two meaning-preserving 
lexical alternatives (e.g. help and facilitate), so that wording choice 
becomes an additional degree of freedom in paragraph layout. The central 
question is whether such alternatives can be exploited to improve 
line-breaking quality under a paragraph-level objective.

Our work makes two main contributions. First, we conduct an empirical study 
under controlled LuaTeX conditions. For small search spaces, we perform exact 
brute-force evaluation over all alternative combinations; for larger search 
spaces, we evaluate a fixed number of random samples. Overall we can see 
substantial improvement, both numerically and visually. Moreover, we observe 
that random sampling works surprisingly well.

Second, we present an exact dynamic programming formulation for a simplified 
but nontrivial version of the problem. The algorithm jointly optimizes 
lexical choice, line breaks, hyphenation, and line justification cost without 
enumerating all lexical assignments explicitly. This shows that lexical 
variation can be incorporated directly into the algorithmic structure of 
paragraph line breaking.

Taken together, these results suggest that meaning-preserving lexical 
substitution is a genuine control variable for paragraph formatting. More 
broadly, the thesis points toward typographic systems that do not only 
optimize where to break a fixed paragraph, but also optimize which 
semantically acceptable realization of that paragraph should be set.

Date            : 29 April 2026 (Wednesday)

Time            : 14:00 - 14:40

Venue           : Room 2126A (near Lift 19), HKUST

Advisor         : Prof. SANDER Pedro

2nd Reader      : Dr. CHEN Qifeng