Contents

• Acknowledgements
• Introduction
  • Scope and contributions of the thesis
  • Organization of the thesis
• Electronic publishing
  • Visual publishing on the electronic media
  • Electronic newspapers---state of the art and future visions
  • Present tools and systems supporting electronic publishing and automatic pagination
    • Presentation of data
      • SGML.
      • HTML and WWW.
      • DSSSL.
    • Tools for interactive layout design
    • Tools for automatic pagination
• Automation of pagination
  • Pagination
    • Page layout
      • Saving space
      • Cognitive considerations
      • Aesthetic considerations.
  • Automatic pagination
    • Justification and objects of automatic pagination
      • Limited production resources.
      • Need for fast delivery but some visuality.
      • Customer-dependent content.
      • Variable viewing dimensions.
    • Tasks
      • Selection of material.
      • Pagination.
• General layout problem---history and theoretical approaches
  • Analysis of the layout problem
    • Type 1: Fixed size, fixed contents
    • Type 2: Varying size, fixed contents
    • Type 3: Fixed size, varying contents
  • Algorithmic approaches
    • Graph-theoretic approach
      • Heuristic graph searches.
    • Knapsack-problems and bin-packing
    • Genetic algorithms
    • Simulated annealing
      • From metaphor to algorithm.
      • Practical implementation.
      • Applications of simulated annealing to layout generation.
• Case studies
  • Problem description
  • Selected approaches
  • Fax newspaper prototype
    • VTT's VIPÊ
    • Extensions to VIPÊ
      • Pagination of variable-sized blocks.
      • Adding user control to the pagination results.
      • Implemented controls.
  • Simulated annealing, experiment 1: straightforward implementation
    • Selection of material---variable-base adder
      • Generation of prospective combinations.
      • Testing and discarding unsuitable combinations.
    • Creating the layout by simulated annealing
      • State space.
      • State transitions.
      • Annealing schedule.
      • Cost function.
    • Results
      • Lessons learned from the approach.
  • Simulated annealing, experiment 2: utilizing domain knowledge
    • State transitions.
    • Annealing schedule.
    • Cost function.
    • Analysis of the approach.
    • Results
  • Comparison of approaches
    • VIPÊ .
    • SA1.
    • SA2.
• Conclusions and future directions
  • Automatic pagination and electronic publishing
  • Simulated annealing
• References
• About this document ...

Acknowledgements

I would like to thank my instructor Ilkka Karanta for discussions and insightful comments about pagination in general and the theoretical foundations of this work. Warm thanks also to the other people at the Intelligent Pagination Group at Technical Research Centre of Finland (VTT), especially Teppo Veijonen, for valuable advise into the secrets of VIPÊ and newspaper pagination, as well as many good questions and helpful comments about the whole. Special thanks to Janne Sinkkonen who had the patience to read through several drafts of this paper, and who offered an invaluable discussion partner especially for the sections concerning simulated annealing. Thanks also to the other people who read and commented on the work, Timo Honkela, my other instructor Juha Ylä-Jääski and my supervisor Markku Syrjänen.

The work described in this thesis was supported by Technical Research Centre of Finland (VTT).