Automatic float placement in multi-column documents

ABSTRACT

Multi-column layout with horizontal scrolling has a number of advantages over the standard model (single column with vertical scrolling) for on-line document layout. However, one difficulty with the multi-column model is the need for good automatic placement of floating figures. We identify reasonable aesthetic criteria for their placement, and then give a dynamic-programming-like algorithm for finding an optimal layout with respect to these criteria. We also investigate an A* based approach and give two variants differing in the choice of heuristic. We find that one of the A* based approaches is faster than the dynamic programming approach and, if a "window" of optimization is used, fast enough for moderately sized documents.

REFERENCES

• 1: A. Brüggemann-Klein, R. Klein, and S. Wohlfeil. Pagination reconsidered. In Electronic Publishing, volume 8, pages 139--152, 1995.
• 2: J. Felici. The Complete Manual of Typography. Peach Pit Press, Berkeley, CA, 2003.
• 3: Nathan Hurst , Kim Marriott , Peter Moulder, Toward tighter tables, Proceedings of the 2005 ACM symposium on Document engineering, November 02-04, 2005, Bristol, United Kingdom [doi>10.1145/1096601.1096623]
• 4: Nathan Hurst , Kim Marriott , Peter Moulder, Minimum sized text containment shapes, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands [doi>10.1145/1166160.1166165]
• 5: Charles Jacobs , Wilmot Li , Evan Schrier , David Bargeron , David Salesin, Adaptive grid-based document layout, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 6: H. W. Lie. CSS3 module: Multi-column layout. Jan. 2001. http://www.w3.org/TR/2001/WD-css3-multicol-20010118/.
• 7: F. Mittelbach. Formatting documents with floats - a new algorithm for LATEX2e*. TUGboat, 21, 2000.
• 8: Michael Frederick Plass, Optimal pagination techniques for automatic typesetting systems, Stanford University, Stanford, CA, 1981
• 9: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Format and notation

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Photocomposition/typesetting

General Terms:
Algorithms

Keywords:
floating figure, multi-column layout, optimization techniques