Review of automatic document formatting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Review of automatic document formatting

Full text

Pdf (440 KB)

Source

Document Engineering archive
Proceedings of the 9th ACM symposium on Document engineering table of contents

Munich, Germany

SESSION: Document presentation (I) -- formatting, printing and layout table of contents

Pages 99-108

Year of Publication: 2009

ISBN:978-1-60558-575-8

Authors

Nathan Hurst	Adobe Systems Inc., San Francisco, CA, USA
Wilmot Li	Adobe Systems Inc., San Francisco, CA, USA
Kim Marriott	Monash University, Victoria, Australia

Sponsors

SIGDOC: ACM Special Interest Group for Design of Communications
SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 51, Downloads (12 Months): 51, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1600193.1600217 What is a DOI?

ABSTRACT

We review the literature on automatic document formatting with an emphasis on recent work in the field. One common way to frame document formatting is as a constrained optimization problem where decision variables encode element placement, constraints enforce required geometric relationships, and the objective function measures layout quality. We present existing research using this framework, describing the kind of optimization problem being solved and the basic optimization techniques used to solve it. Our review focuses on the formatting of primarily textual documents, including both micro- and macro-typographic concerns. We also cover techniques for automatic table layout. Related problems such as widget and diagram layout, as well as temporal layout issues that arise in multimedia documents are outside the scope of this review.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. J. Anderson and S. Sobti. The table layout problem. In COMPGEOM: Annual ACM Symposium on Computational Geometry, pages 115--123, 1999.
	2	G. Asher. Inside type & set. TUGBoat, 13, 1992.
	3	G. J. Badros, A. Borning, K. Marriott, and P. Stuckey. Constraint cascading style sheets for the web. In Proceedings of the 1999 ACM Conference on User Interface Software and Technology, pages 73--82, New York, Nov. 1999. ACM.
	4	G. J. Badros, J. J. Tirtowidjojo, K. Marriott, B. Meyer, W. Portnoy, and A. Borning. A constraint extension to scalable vector graphics. In WWW '01: Proceedings of the 10th international conference on World Wide Web, pages 489--498, New York, NY, USA, 2001. ACM Press.
	5	S. Baluja. Browsing on small screens: recasting web-page segmentation into an efficient machine learning framework. In WWW '06: Proceedings of the 15th international conference on World Wide Web, pages 33--42, New York, NY, USA, 2006. ACM.
	6	J. Bateman, J. Kleinz, T. Kamps, and K. Reichenberger. Towards constructive text, diagram, and layout generation for information presentation. Comput. Linguist., 27(3):409--449, 2001.
	7	P. Baudisch, B. Lee, and L. Hanna. Fishnet, a fisheye web browser with search term popouts: a comparative evaluation with overview and linear view. In AVI '04: Proceedings of the working conference on Advanced visual interfaces, pages 133--140, New York, NY, USA, 2004. ACM.
	8	R. J. Beach. Setting tables and illustrations with style. PhD thesis, University of Waterloo, 1985.
	9	N. Beaumont. Fitting a table to a page using non-linear optimization. Asia-Pacific Journal of Operational Research, 21(2):259--270, 2004.
	10	D. P. Bertsekas. Nonlinear Programming. Athena Scientific, September 1999.
	11	S. Björk, L. E. Holmquist, J. Redström, I. Bretan, R. Danielsson, J. Karlgren, and K. Franzén. West: a web browser for small terminals. In UIST '99: Proceedings of the 12th annual ACM symposium on User interface software and technology, pages 187--196, New York, NY, USA, 1999. ACM.
	12	A. Borning, R. Lin, and K. Marriott. Constraints for the web. In Proceedings of ACM MULTIMEDIA'97, pages 173--182, Nov. 1997.
	13	A. Borning, R. Lin, and K. Marriott. Constraint-based document layout for the web. Multimedia Systems, 8(3):177--189, 2000.
	14	B. Bos. Personal communication, May 2009.
	15	B. Bos, H. Lie, C. Lilley, and I. Jacobs. Cascading Style Sheets, level 2 CSS2 Specification. W3C Recommendation. http://www.w3.org/TR/REC-CSS2, 1998.
	16	C. Braganza, K. Marriott, P. Moulder, M. Wybrow, and T. Dwyer. Scrolling behaviour with single- and multi-column layout. In ACM Conference on the World Wide Web (WWW 2002), pages 831--840, 2009.
	17	A. Brüggemann-Klein, R. Klein, and S. Wohlfeil. Pagination reconsidered. In Electronic Publishing, volume 8, pages 139--152, 1995.
	18	Y. Chen, W.-Y. Ma, and H.-J. Zhang. Detecting web page structure for adaptive viewing on small form factor devices. In WWW '03: Proceedings of the 12th international conference on World Wide Web, pages 225--233, New York, NY, USA, 2003. ACM.
	19	J. B. S. de Oliveira. Two algorithms for automatic document page layout. In DocEng '08: Proceeding of the eighth ACM symposium on Document engineering, pages 141--149, New York, NY, USA, 2008. ACM.
	20	J. D. DeTreville. An Analytical Approach to Computerized News Layout for Newspapers. PhD thesis, MIT, Cambridge, MA, USA, 1978.
	21	A. Di Iorio, L. Furini, F. Vitali, J. Lumley, and T. Wiley. Higher-level layout through topological abstraction. In DocEng '08: Proceeding of the eighth ACM symposium on Document engineering, pages 90--99, New York, NY, USA, 2008. ACM.
	22	D. Eppstein, Z. Galil, R. Giancarlo, and G. F. Italiano. Sparse dynamic programming ii: convex and concave cost functions. J. ACM, 39(3):546--567, 1992.
	23	S. K. Feiner. A grid-based approach to automating display layout. In Proceedings on Graphics interface '88, pages 192--197, Toronto, Ont., Canada, Canada, 1988. Canadian Information Processing Society.
	24	R. Furuta. Important papers in the history of document preparation systems: basic sources. Electronic Publishing, 5:19--44, 1992.
	25	R. Furuta, J. Scofield, and A. Shaw. Document formatting systems: survey, concepts, and issues. ACM Computing Surveys (CSUR), 14(3):417--472, 1982.
	26	F. Glover and G. Kochenberger. Handbook of metaheuristics. Springer, 2003.
	27	E. Goldenberg. Automatic layout of variable-content print data. Technical Report 286, Hewlett-Packard Laboratories, Oct. 2002.
	28	W. H. Graf. The constraint-based layout framework laylab and its applications. In In Proceedings of ACM Workshop on Effective Abstractions in Multimedia, Layout and Interaction. ACM, 1995.
	29	W. H. Graf, S. Neurohr, and R. Goebel. Ypps - a constraint-based tool for the pagination of yellow-page directories. In Proceedings of the KI-96 Workshop on Declarative Constraint Programming, pages 87--97, 1996.
	30	S. J. Harrington, J. F. Naveda, R. P. Jones, P. Roetling, and N. Thakkar. Aesthetic measures for automated document layout. In DocEng '04: Proceedings of the 2004 ACM symposium on Document engineering, pages 109--111, New York, NY, USA, 2004. ACM.
	31	W. Hegazy and J. Gourlay. Optimal line breaking in music. In Document Manipulation and Typography: Proceedings of the International Conference on Electronic Publishing, Document Manipulation, and Typography, pages 157--169. Cambridge University Press, 1988.
	32	R. D. Hersch and C. Bétrisey. Method for producing visually evenly spaced typographic characters. US Patent, 1996.
	33	D. S. Hirschberg and L. L. Larmore. The least weight subsequence problem. SIAM J. Comput., 16(4):628--638, 1987.
	34	N. Hurst. Better automatic layout of documents. PhD thesis, Monash University, Department of Computer Science, May 2009.
	35	N. Hurst and K. Marriott. Satisficing scrolls: a shortcut to satisfactory layout. In DocEng '08: Proceeding of the eighth ACM symposium on Document engineering, pages 131--140, New York, NY, USA, 2008. ACM.
	36	N. Hurst, K. Marriott, and D. Albrecht. Solving the simple continuous table layout problem. In DocEng '06: Proceedings of the 2006 ACM symposium on Document engineering, pages 28--30, New York, NY, USA, 2006. ACM Press.
	37	N. Hurst, K. Marriott, and P. Moulder. Cobweb: A constraint-based web browser. In M. J. Oudshoorn, editor, ACSC, volume 16 of CRPIT, pages 247--254. Australian Computer Society, 2003.
	38	N. Hurst, K. Marriott, and P. Moulder. Toward tighter tables. In DocEng '05: Proceedings of the 2005 ACM symposium on Document engineering, pages 74--83, New York, NY, USA, 2005. ACM Press.
	39	N. Hurst, K. Marriott, and P. Moulder. Minimum sized text containment shapes. In DocEng '06: Proceedings of the 2006 ACM symposium on Document engineering, pages 3--12, New York, NY, USA, 2006. ACM Press.
	40	C. Jacobs, W. Li, and D. Salesin. Adaptive document layout via manifold content. In Proceedings of Workshop on Web Document Analysis, Edinburgh, 2003.
	41	C. Jacobs, W. Li, E. Schrier, D. Bargeron, and D. Salesin. Adaptive grid-based document layout. ACM Trans. Graph., 22(3):838--847, 2003.
	42	R. Johari, J. Marks, A. Partovi, and S. Shieber. Automatic yellow-pages pagination and layout. Journal of Heuristics, 2:321--342, 1997.
	43	M. Jourdan, N. Layaïda, C. Roisin, L. Sabry-Ismaïl, and L. Tardif. Madeus, and authoring environment for interactive multimedia documents. In Proceedings of the sixth ACM international conference on Multimedia, pages 267--272. ACM New York, NY, USA, 1998.
	44	T. Kamps and K. Reichenberger. Automatic layout based on formal semantics. In AVI '94: Proceedings of the workshop on Advanced visual interfaces, pages 231--233, New York, NY, USA, 1994. ACM.
	45	H.-K. Kan. A Computerized Template-driven News-layout System for Newspapers. PhD thesis, MIT, Department of Electrical Engineering, 1977.
	46	P. Karow. Two Decades of Typographic Research at URW: A Retrospective. In Electronic Publishing, Artistic Imaging, and Digital Typography '98, volume 1190 of LNCS, pages 265--280. Springer-Verlag, 1998.
	47	B. W. Kernighan. A troff tutorial, unix version 7 manual. Technical report, Bell Laboratories Computing Science, June 1978.
	48	D. E. Knuth. The TEXbook. Addison-Wesley, Reading, Massachusetts, 1984.
	49	D. E. Knuth. Digital Typography. Cambridge University Press, New York, NY, USA, 1997.
	50	D. E. Knuth and M. F. Plass. Breaking paragraphs into lines. In Software - Practice and Experience, 11(11), pages 1119--1184, Nov. 1982.
	51	J. Kong, M. Qiu, and K. Zhang. Authoring multimedia documents through grammatical specifications. In ICME '03: Proceedings of the 2003 International Conference on Multimedia and Expo, pages 629--632, Washington, DC, USA, 2003. IEEE Computer Society.
	52	H. Lam and P. Baudisch. Summary thumbnails: readable overviews for small screen web browsers. In CHI '05: Proceedings of the SIGCHI conference on Human factors in computing systems, pages 681--690, New York, NY, USA, 2005. ACM.
	53	J. Lau and P. Karow. hz-program: Micro-typography for advanced typesetting. In SID Symposium 1993, pages 58--62, 1993.
	54	H. W. Lie. The electronic broadsheet: all the news that fits the display, 1991. SM Thesis, MIT Media Lab.
	55	X. Lin. Active layout engine: Algorithms and applications in variable data printing. Computer-Aided Design, 38(5):444--456, 2006.
	56	X. Lin. Predictive Text Fitting. Lecture Notes in Computer Science, 4073:13--23, 2006.
	57	G. Loureiro and F. Azevedo. Constrained xsl formatting objects for adaptive documents. In DocEng '05: Proceedings of the 2005 ACM symposium on Document engineering, pages 95--97, New York, NY, USA, 2005. ACM Press.
	58	J. Lumley, R. Gimson, and O. Rees. Extensible layout in functional documents. In Proceedings of SPIE, volume 6076, pages 177--188, 2006.
	59	J. Lumley, R. Gimson, and O. Rees. Resolving layout interdependency with presentational variables. In DocEng '06: Proceedings of the 2006 ACM symposium on Document engineering, pages 95--97, New York, NY, USA, 2006. ACM.
	60	C. Lutteroth and G. Weber. User interface layout with ordinal and linear constraints. In AUIC '06: Proceedings of the 7th Australasian User Interface Conference, pages 53--60. Australian Computer Society, Inc., 2006.
	61	K. Marriott, B. Meyer, and L. Tardif. Fast and efficient client-side adaptivity for svg. In ACM Conference on the World Wide Web (WWW 2002), 2002.
	62	K. Marriott, P. Moulder, and N. Hurst. Automatic float placement in multi-column documents. In DocEng '07: Proceedings of the 2007 ACM symposium on Document engineering, New York, NY, USA, 2007. ACM Press.
	63	C. McCormack, K. Marriott, and B. Meyer. Adaptive layout using one-way constraints in SVG. In Proceedings of third Annual Conference on Scalable Vector Graphics, SVG Open, 2004.
	64	F. Mittelbach. Formatting documents with floats - a new algorithm for LATEX2µ*. TUGboat, 21, 2000.
	65	F. Mittelbach and C. Rowley. The pursuit of quality - how can automated typesetting achieve the highest standards of craft typography? In EP92 (Proceedings of Electronic Publishing), pages 261--273. Cambridge University Press, 1992.
	66	H.-W. Nienhuys and J. Nieuwenhuizen. Lilypond, a system for automated music engraving. In Proceedings of the XIV Colloquium on Musical Informatics (XIV CIM 2003), Firenze, Italy, May 2003.
	67	J. Nocedal and S. J. Wright. Numerical Optimization. Springer, New York, 1999.
	68	K. O'Hara, A. Sellen, and R. Bentley. Supporting memory for spatial location while reading from small displays. In CHI '99: CHI '99 extended abstracts on Human factors in computing systems, pages 220--221, New York, NY, USA, 1999. ACM.
	69	M. F. Plass. Optimal pagination techniques for automatic typesetting systems. PhD thesis, Stanford University, June 1981.
	70	L. Purvis, S. Harrington, B. O'Sullivan, and E. C. Freuder. Creating personalized documents: an optimization approach. In DocEng '03: Proceedings of the 2003 ACM symposium on Document engineering, pages 68--77, New York, NY, USA, 2003. ACM Press.
	71	D. Raggett, A. L. Hors, and I. Jacobs. HTML 4.01 Specification, section 'Autolayout Algorithm'. http://www.w3.org/TR/html4/appendix/notes.html#h-B.5.2, 1999.
	72	V. Roto, A. Popescu, A. Koivisto, and E. Vartiainen. Minimap: a web page visualization method for mobile phones. In CHI '06: Proceedings of the SIGCHI conference on Human Factors in computing systems, pages 35--44, New York, NY, USA, 2006. ACM.
	73	S. Russell and P. Norvig. Artificial Intelligence: a Modern Approach. Prentice Hall, 2nd edition, 2002.
	74	E. Schrier, M. Dontcheva, C. Jacobs, G. Wade, and D. Salesin. Adaptive layout for dynamically aggregated documents. In Proc. of the 13th Intl. Conf. on Intelligent User Interfaces, pages 99--108. ACM, 2008.
	75	H. T. Thành. Micro-typographic extensions to the TEX typesetting system (doctoral dissertation). TUGBoat, 21, 2000.
	76	C. Vanoirbeek. Formatting structured tables. In EP92 (Proceedings of Electronic Publishing), pages 291--309. Cambridge University Press, 1992.
	77	X. Wang and D. Wood. Tabular formatting problems. In 3rd Principles of Document Processing, pages 171--181, 1996.
	78	L. Weitzman and K. Wittenburg. Relational grammars for interactive design. In IEEE Symposium on Visual Languages, pages 4--11, 1993.
	79	L. Weitzman and K. Wittenburg. Automatic generation of multimedia documents using relational grammars. In Proceedings of 2nd ACM Conference on Multimedia, 1994.
	80	X. Xie, G. Miao, R. Song, J.-R. Wen, and W.-Y. Ma. Efficient browsing of web search results on mobile devices based on block importance model. In PERCOM '05: Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, pages 17--26, Washington, DC, USA, 2005. IEEE Computer Society.
	81	H. Zapf. About micro-typography and the hz-program. Electronic Publishing, 6(3):283--288, Sept. 1993