Better automatic layout of documents

One of the most common tasks performed by computers is document generation. However, automatic document generation is hard. While many WYSIWYG (What You See Is What You Get) tools make document generation easier for users, the tools are labour intensive, unable to adapt to presentation changes and do not deal with substantial changes in content at all. In this thesis we explore the issues that make automatic document generation difficult, and in particular, look at the issue of handling text. A statistically accurate approximation to text layout behaviour based around area is developed. The approximation is used to efficiently adjust shapes to neatly contain text, find compact table layouts and place floating figures. This thesis examines a number of interesting new approaches for automatic document layout presented in the context of optimisation technology. Significant results include a prototype browser based on one-way constraint solver technology, a continuous model for text layout prediction and a new active-set based approach for minimising table layout area. As hinted, one of the most difficult aspects of layout-as-minimisation is the efficient handling of text. We have considered text as an incompressible two dimensional fluid with statistically predictable variation in area. This approximation was shown to be helpful for one-dimensional, multi-dimensional convex and non-convex minimisation problems occurring in many practical applications of automatic layout. By using constrained minimisation we can couch the layout problem in terms of a combined goal function and thus move some way towards an effective overall strategy. However, combining such complex goal functions makes optimisation difficult. We look at a general approach of relaxation of text behaviour to improve layout optimisation.