Satisficing scrolls: a shortcut to satisfactory layout

ABSTRACT

We present at a new approach to finding aesthetically pleasing page layouts. We do not aim to find an optimal layout, rather the aim is to find a layout which is not obviously wrong. We consider vertical scroll-like layout with floating figures referenced within the text where floats can have alternate sizes, may be optional, move from one side to the other and change their order. We also allow pagination. Our approach is to use a randomised local search algorithm to explore different configurations of floats, i.e. choice of floats and relative ordering. For a particular float configuration we use an efficient gradient projection-like continuous optimization algorithm. The resulting system is fast and provides an efficient warm start option to improve interactive support.

REFERENCES

• 1: D. P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.
• 2: S. Binato, H. Jr, and M. Resende. Greedy randomized adaptive path relinking.
• 3: A. Brüggemann-Klein, R. Klein, and S. Wohlfeil. Pagination reconsidered. In Electronic Publishing, volume 8, pages 139--152, 1995.
• 4: Tim Dwyer , Yehuda Koren , Kim Marriott, IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.821-828, September 2006 [doi>10.1109/TVCG.2006.156]
• 5: T. Dwyer, K. Marriott, and P. J. Stuckey. Fast node overlap removal. In GD2005: 13th International Symposium of Graph Drawing 2005, volume 3843 of Lecture Notes in Computer Science, pages 153--164. Springer Berlin, 2006.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: E. Goldenberg. Automatic layout of variable-content print data. Technical Report 286, Hewlett-Packard Laboratories, Oct. 2002.
• 8: Nathan Hurst , Kim Marriott, Approximating text by its area, Proceedings of the 2007 ACM symposium on Document engineering, August 28-31, 2007, Winnipeg, Manitoba, Canada [doi>10.1145/1284420.1284458]
• 9: N. J. Hurst. Better automatic layout of documents. PhD thesis, Monash University, pending.
• 10: 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
• 11: D. E. Knuth and M. F. Plass. Breaking paragraphs into lines. In Software-Practice and Experience, 11(11), pages 1119--1184, Nov. 1982.
• 12: Kim Marriott , Peter Moulder , Nathan Hurst, Automatic float placement in multi-column documents, Proceedings of the 2007 ACM symposium on Document engineering, August 28-31, 2007, Winnipeg, Manitoba, Canada [doi>10.1145/1284420.1284455]
• 13: Michael Frederick Plass, Optimal pagination techniques for automatic typesetting systems, Stanford University, Stanford, CA, 1981
• 14: Lisa Purvis , Steven Harrington , Barry O'Sullivan , Eugene C. Freuder, Creating personalized documents: an optimization approach, Proceedings of the 2003 ACM symposium on Document engineering, November 20-22, 2003, Grenoble, France [doi>10.1145/958220.958234]
• 15: H. A. Simon. A behavioral model of rational choice. The Quarterly Journal of Economics, 69(1):99--118, 1955.
• 16: L. Weitzman , Kent Wittenburg, Automatic presentation of multimedia documents using relational grammars, Proceedings of the second ACM international conference on Multimedia, p.443-451, October 15-20, 1994, San Francisco, California, United States [doi>10.1145/192593.192718]

INDEX TERMS

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

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

General Terms:
Algorithms

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