Abstract/Details

OPTIMAL PAGINATION TECHNIQUES FOR AUTOMATIC TYPESETTING SYSTEMS


1981 1981

Other formats: Order a copy

Abstract (summary)

This thesis considers how to use a computer to break a document into pages suitable for printing. Although this problem is easy to solve when the document consists of just text, it becomes complicated when footnotes, displays, and figures are introduced. These elements add some freedom of choice in the way breaks are chosen, since the white space around the displays and the exact placement of the figures can be decided by the pagination algorithm. Out of the many possible ways to paginate such a document, the pagination algorithm should pick the one that is in some sense optimal. The approach taken here is to define a badness function that depends on the way the document is broken up, and then to design an algorithm to find a way to minimize the value of this function.

The document is modelled by two lists, the text list and the figure list. Each item in the text list is either a 'box', corresponding to something that will print such as a line of text, a 'glue' item, corresponding to the white space between the lines, a 'penalty' item, corresponding to a legal place to break the list, or a 'citation', marking a reference to one of the figures. The items in the figure list indicate the size of each figure, and by how much each figure is allowed to stretch or shrink. This model is based on the one used in the TEX typesetting system.

The optimizing pagination algorithm uses dynamic programming to find, for each i, j, and k, the best way to put the first i lines of text and the first j figures onto the first k pages; to make the program run in a reasonable amount of time, this calculation includes only those subproblems that are feasible, i.e., likely to lead to a solution with a small badness value.

The badness function must be chosen carefully in order to get a problem that can be solved by these techniques. For certain simple badness functions, the pagination problem is NP-complete; two such functions are described in the thesis.

Indexing (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences
Title
OPTIMAL PAGINATION TECHNIQUES FOR AUTOMATIC TYPESETTING SYSTEMS
Author
PLASS, MICHAEL FREDERICK
Number of pages
78
Publication year
1981
Degree date
1981
School code
0212
Source
DAI-B 42/05, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
University/institution
Stanford University
University location
United States -- California
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
8124134
ProQuest document ID
303197709
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/303197709
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.