Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On the Pagination of Complex Documents
| |
|
On the Pagination of Complex Documents
Anne Brüggemann-Klein7  , Rolf Klein8 and Stefan Wohlfeil9
| (7) |
Technische Universität München, Arcisstr. 21, D-80290 München, Germany |
| (8) |
Universität Bonn, Römerstr.164, D-53117 Bonn, Germany |
| (9) |
Fachhochschule Hannover, Ricklinger Stadtweg 118, D-30163 Hannover, Germany |
Abstract
The pagination problem of complex documents is in placing text and floating objects on pages in such a way that each object
appears close to, but not before, its text reference. Current electronic formatting systems do not offer the pagination quality
provided by human experts in traditional bookprinting. One reason is that a good placement of text and floating objects cannot
be achieved in a single pass over the input. We show that this approach works only in a very restricted document model; but
in a realistic setting no online algorithm can approximate optimal pagination quality.
Globally computing an optimal pagination critically depends on the measure of quality used. Some measures are known to render
the problem NP-hard, others cause unwanted side effects. We propose to use the total number of page turns necessary for reading
the document and for looking up all referenced objects. This objective function can be optimized by dynamic programming, in
time proportional to the number of text blocks times the number of floating objects. Our implementation takes less than one
minute for formatting a chapter of 30 pages. The results compare favorably with layouts obtained by Word, FrameMaker, or LATEX, that were fine-tuned by expert users.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|