in the following description of the preferred embodiments of the present invention , reference is made to the accompanying drawings which form a part hereof , and in which is shown by way of illustration specific embodiments in which the invention may be practiced . it is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention . fig1 illustrates an example of a suitable computing system environment 100 on which the invention may be implemented . the computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention . neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100 . the invention is operational with numerous other general purpose or special purpose computing system environments or configurations . examples of well known computing systems , environments , and / or configurations that may be suitable for use with the invention include , but are not limited to , personal computers , server computers , hand - held or laptop devices , multiprocessor systems , microprocessor - based systems , set top boxes , programmable consumer electronics , network pcs , minicomputers , mainframe computers , distributed computing environments that include any of the above systems or devices , and the like . the invention may be described in the general context of computer - executable instructions , such as program modules , being executed by a computer . generally , program modules include routines , programs , objects , components , data structures , etc . that perform particular tasks or implement particular abstract data types . the invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network . in a distributed computing environment , program modules may be located in both local and remote computer storage media including memory storage devices . with reference to fig1 , an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer 110 . components of computer 110 may include , but are not limited to , a processing unit 120 , a system memory 130 , and a system bus 121 that couples various system components including the system memory to the processing unit 120 . the system bus 121 may be any of several types of bus structures including a memory bus or memory controller , a peripheral bus , and a local bus using any of a variety of bus architectures . by way of example , and not limitation , such architectures include industry standard architecture ( isa ) bus , micro channel architecture ( mca ) bus , enhanced isa ( eisa ) bus , video electronics standards association ( vesa ) local bus , and peripheral component interconnect ( pci ) bus also known as mezzanine bus . computer 110 typically includes a variety of computer readable media . computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media , removable and non - removable media . by way of example , and not limitation , computer readable media may comprise computer storage media and communication media . computer storage media includes both volatile and nonvolatile , removable and non - removable media implemented in any method or technology for storage of information such as computer readable instructions , data structures , program modules or other data . computer storage media includes , but is not limited to , ram , rom , eeprom , flash memory or other memory technology , cd - rom , digital versatile disks ( dvd ) or other optical disk storage , magnetic cassettes , magnetic tape , magnetic disk storage or other magnetic storage devices , or any other medium which can be used to store the desired information and which can be accessed by computer 110 . communication media typically embodies computer readable instructions , data structures , program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media . the term “ modulated data signal ” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal . by way of example , and not limitation , communication media includes wired media such as a wired network or direct - wired connection , and wireless media such as acoustic , rf , infrared and other wireless media . combinations of the any of the above should also be included within the scope of computer readable media . the system memory 130 includes computer storage media in the form of volatile and / or nonvolatile memory such as read only memory ( rom ) 131 and random access memory ( ram ) 132 . a basic input / output system 133 ( bios ), containing the basic routines that help to transfer information between elements within computer 110 , such as during start - up , is typically stored in rom 131 . ram 132 typically contains data and / or program modules that are immediately accessible to and / or presently being operated on by processing unit 120 . by way of example , and not limitation , fig1 illustrates operating system 134 , application programs 135 , other program modules 136 , and program data 137 . the computer 110 may also include other removable / non - removable , volatile / nonvolatile computer storage media . by way of example only , fig1 illustrates a hard disk drive 141 that reads from or writes to non - removable , nonvolatile magnetic media , a magnetic disk drive 151 that reads from or writes to a removable , nonvolatile magnetic disk 152 , and an optical disk drive 155 that reads from or writes to a removable , nonvolatile optical disk 156 such as a cd rom or other optical media . other removable / non - removable , volatile / nonvolatile computer storage media that can be used in the exemplary operating environment include , but are not limited to , magnetic tape cassettes , flash memory cards , digital versatile disks , digital video tape , solid state ram , solid state rom , and the like . the hard disk drive 141 is typically connected to the system bus 121 through an non - removable memory interface such as interface 140 , and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface , such as interface 150 . the drives and their associated computer storage media discussed above and illustrated in fig1 , provide storage of computer readable instructions , data structures , program modules and other data for the computer 110 . in fig1 , for example , hard disk drive 141 is illustrated as storing operating system 144 , application programs 145 , other program modules 146 , and program data 147 . note that these components can either be the same as or different from operating system 134 , application programs 135 , other program modules 136 , and program data 137 . operating system 144 , application programs 145 , other program modules 146 , and program data 147 are given different numbers here to illustrate that , at a minimum , they are different copies . a user may enter commands and information into the computer 110 through input devices such as a keyboard 162 and pointing device 161 , commonly referred to as a mouse , trackball or touch pad . other input devices ( not shown ) may include a microphone , joystick , game pad , satellite dish , scanner , or the like . these and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus 121 , but may be connected by other interface and bus structures , such as a parallel port , game port or a universal serial bus ( usb ). a monitor 191 or other type of display device is also connected to the system bus 121 via an interface , such as a video interface 190 . in addition to the monitor , computers may also include other peripheral output devices such as speakers 197 and printer 196 , which may be connected through an output peripheral interface 195 . of particular significance to the present invention , a camera 163 ( such as a digital / electronic still or video camera , or film / photographic scanner ) capable of capturing a sequence of images 164 can also be included as an input device to the personal computer 110 . further , while just one camera is depicted , multiple cameras could be included as an input device to the personal computer 110 . the images 164 from the one or more cameras are input into the computer 110 via an appropriate camera interface 165 . this interface 165 is connected to the system bus 121 , thereby allowing the images to be routed to and stored in the ram 132 , or one of the other data storage devices associated with the computer 110 . however , it is noted that image data can be input into the computer 110 from any of the aforementioned computer - readable media as well , without requiring the use of the camera 163 . the computer 110 may operate in a networked environment using logical connections to one or more remote computers , such as a remote computer 180 . the remote computer 180 may be a personal computer , a server , a router , a network pc , a peer device or other common network node , and typically includes many or all of the elements described above relative to the computer 110 , although only a memory storage device 181 has been illustrated in fig1 . the logical connections depicted in fig1 include a local area network ( lan ) 171 and a wide area network ( wan ) 173 , but may also include other networks . such networking environments are commonplace in offices , enterprise - wide computer networks , intranets and the internet . when used in a lan networking environment , the computer 110 is connected to the lan 171 through a network interface or adapter 170 . when used in a wan networking environment , the computer 110 typically includes a modem 172 or other means for establishing communications over the wan 173 , such as the internet . the modem 172 , which may be internal or external , may be connected to the system bus 121 via the user input interface 160 , or other appropriate mechanism . in a networked environment , program modules depicted relative to the computer 110 , or portions thereof , may be stored in the remote memory storage device . by way of example , and not limitation , fig1 illustrates remote application programs 185 as residing on memory device 181 . it will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used . the exemplary operating environment having now been discussed , the remaining parts of this description section will be devoted to a description of the program modules embodying the invention . in this section , the adaptive document layout system and method is described . specifically , this section address the way document content and structure is represented . additionally , the system and method of authoring documents via an exemplary graphic user interface ( gui ), the document layout engine and a novel text - breaking algorithm are also discussed . the term content is used to refer to any portion of a document — for example , a piece of text , an image , a set of html links , a set of formatting instructions , or any combination thereof . content can be nested hierarchically , as in a figure that contains an associated caption . manifold content refers to alternate versions of content . to represent manifold content , a tree data structure , called the document tree , is used , as shown in fig2 . as typical , a tree data structure is accessed beginning at the root node 202 ( the distinguished initial or fundamental item of a tree and the only item which has no parent ). the tree is composed of nodes . each node of the tree represents a unit of reference in the data structure , a collection of information that must be kept at a single memory location . each node is either a leaf 204 ( a terminal or “ bottom ” item of a tree , i . e ., an item with no child ) or an internal node 206 . an internal node has one or more child nodes and is called the parent 206 of its child nodes 208 . all children of the same node are siblings . contrary to a physical tree , the root is usually depicted at the top of the structure , and the leaves are depicted at the bottom . in the adaptive document system and method , for simplicity , the content itself is placed at the leaves of the tree . the internal , or structural , nodes of the tree are defined to be one of two kinds : or nodes , which group together alternate versions of content ; and and nodes , which group together an arbitrary series of or and content nodes . the document tree is rooted by an and node , which , assuming a non - empty document , will contain one or more children . while and nodes are not strictly necessary to represent alternate versions of content ( i . e ., or nodes could instead be allowed to appear anywhere within a content node ), it has been found that separating out the structural nodes explicitly , in this way , simplifies the editing algorithms , as described in the next section and the appendix . in practice , an xml file format is used to specify this document structure . xml provides a convenient syntax for organizing the set of nodes in the tree and optionally associating attributes with each node . since traditional documents do not include alternate representations of content , there is only one version of the entire document in these traditional documents . however , there can be many different versions of a multi - representation document corresponding to all combinations of its alternate content . such versions are referred to as document views . fig3 provides a diagram showing an example of how document content is represented as a document tree . consider a “ document ” consisting of a single sentence , s 302 . supposing the document author specifies an alternate version p ′ 304 of a phrase p 306 contained within s 302 . this new content is represented by replacing p with an or node 308 whose children are p and p ′ ( fig3 ). an or node groups together alternate versions of content . thus , only one child of an or node will appear in the document . extending this example , as shown in fig4 , suppose s 402 is contained within paragraph q 406 . the author might want to specify a condensed version of s ( called s ′) 414 that might be more appropriate when the document is viewed on a handheld device . this new content is represented by creating another or node 408 whose children are s and s ′ ( fig4 ). note that the s branch of the top - level or contains the phrase - level or node from before . thus , depending on the viewing situation , either s or s ′ may be displayed . if s is chosen , then one of p 410 or p ′ 412 will be displayed . it is easy to see how the tree structure used to represent this simple example can be used to handle a multi - representation document . any piece of content that has multiple authored versions is represented with an or node , and as in the example , the or nodes can be nested . however , it is hypothesized that difficulties in grasping the meaning of highly nested alternate content will discourage authors from creating documents with deep structure . as a result , it is expected the average document tree to be wide rather than deep . although conceptually it is or nodes that define the tree structure , in practice and nodes are also incorporated to stitch together contiguous pieces of content . in contrast to or nodes , an and node &# 39 ; s children all appear in a view of the document . fig5 shows the actual tree for the running example , with one and node 502 used to group the three components of sentence s . q 1 504 and q 2 506 correspond to the content preceding and following the sentence - level or node 508 , and s 1 510 and s 2 512 correspond to the content preceding and following the phrase - level or node 514 . note that two or more content nodes will never be adjacent children of an and node , since this is equivalent to a single node containing all of the content . in addition , and nodes are only used to group different types . two trees are considered equivalent if they can generate identical sets of document views , regardless of differences in structure . fig6 shows an example of two equivalent trees whose nodes are organized differently . a transformation of one of the trees is considered valid as long as the resulting tree is equivalent to the original . xml file format is used to specify the document structure discussed above . xml provides convenient syntax for organizing a set of nodes in a tree and storing attributes associated with each node . the following table indicates how documents are expressed in xml . to represent and and or nodes , the token pairs & lt ; and & gt ; . . . & lt ;/ and & gt ; and & lt ; or ) . . . (/ or & gt ;, are used respectively . each child of an or node is placed between the & lt ; or & gt ; and & lt ;/ or & gt ; tokens and is denoted by the token pair & lt ; rep attributes & gt ; . . . & lt ;/ rep & gt ;. the attributes in the & lt ; rep & gt ; node are used to specify an arbitrary list of any special properties associated with the designated content , such as “ summary version ,” “ in - depth version ,” “ large - type version ,” etc ., which are used to inform the layout . & lt ; div & gt ; nodes are used to denote a collection of content that should be laid out in a rectangular , rather than in line , with other content ( e . g ., a sidebar ). & lt ; div & gt ; nodes are handled much the same as images by the layout engine . table 1 provides a correspondence between a tree element and xml content . manifold content is only useful if it can be authored easily and effectively . indeed , one reasonable objection to the whole adaptive document layout approach might be that it sounds like too much work for authors to be expected to create not just one , but many possible versions of their document . however , with the right authoring tools , this approach is not necessarily so onerous . for one thing , in many cases , the author is already doing this kind of work — adapting a document for several different audiences , for instance , when preparing a journal article from an earlier conference paper . in this case , the adaptive document layout system and method could actually be used to help keep the different versions in synch , rather than having entirely separate documents that have to be maintained and updated in tandem . in addition , as already mentioned , authors commonly make small changes to a document in order to fix up various formatting problems — in this case , the system helps keep around all of the possible versions instead of discarding the earlier ones . finally , while manifold content may not always be worth the cost , it is not difficult to imagine common situations in which a document — say , for example , some advertising copy — is written once for wide distribution over an electronic medium , and for which entering different versions of content is a minimal price to pay for the sake of a far greater visual impact . designing a tool for authoring adaptive documents presents three main challenges . the first difficulty is representing the document such that the user can both understand its tree structure ( or more specifically , what alternate content has been defined ) and maintain a coherent view of the document . clearly , it is important for the author to know which content has alternate versions and what those alternate versions are . at the same time , presenting a coherent view of the content allows the author to see how the document reads and provides a context for editing . the second challenge is designing an intuitive interaction model that allows the user to edit content and specify alternate versions . in other words , the authoring tool must enable the user to modify the document tree . finally , the system should assist the author by suggesting where alternate content could be added to improve layout for some display size . since it is impractical for the user to manually preview and evaluate a document under a wide range of viewing situations , the authoring tool should help the user accomplish the task in a reasonable way . the basic approach to the authoring user interface is to hide most of the document &# 39 ; s structure at any given time and allow the user to interact with what appears to be , at first glance , just a single , linear view of the document . the authoring user interface is composed of two regions , as shown in fig7 . the large pane on the left is the edit pane 702 , in which the linear view of the document appears . the narrower one on the right is the alternate version pane ( also referred to as the alt version pane ) 704 , in which all versions of the currently selected manifold region of the document are shown . each of these two regions includes some visual cues to help the user understand the underlying structure , the current selection state and what interactions are permitted . referring now to fig8 for one exemplary working embodiment of the adaptive layout system and method , areas of manifold content within the edit pane 800 displaying the document are indicated by a faint , purple , dotted line 802 beneath that portion of the content . hovering over an area of manifold content with an input device such as a mouse pointer brings up a small menu 804 with several editing choices . one choice is to “ select ” 806 the version of content beneath the cursor , in which case the content becomes highlighted in yellow 808 and also appears ( also highlighted in yellow ) 810 in the separate , alternate - version pane 812 , to the right side of the edit pane 800 , along with all other ( unhighlighted ) versions of the content 814 a , 814 b . once a version of content is selected , any regions of manifold content within that selection are now indicated with the purple dotted line 818 . ( these correspond to or nodes that are children of the selected content . since or nodes can be nested , manifold regions can also be nested . this means that a given piece of content may belong to a nested collection of manifold regions corresponding to a nested collection of or nodes in the document tree .) if any one of these regions is selected 820 , it and its alternate versions 824 will replace their parent in the alternate - version pane 812 . right - clicking using an input device , such as a mouse , in either pane reveals a menu indicating the available operations for the content beneath the cursor . fig9 indicates how a word w that appears in the edit pane can be part of two different manifold regions . thus , if one tried to underline every different manifold region in the document , some content ( such as w ) would have to be underlined more than once . furthermore , selecting a particular manifold region might be difficult , since clicking on a multiple underlined piece of content would identify more than one candidate manifold region to be selected . partly because of these issues and partly in an attempt to avoid over cluttering the interface of the system , in one working embodiment , every manifold region in the document is not underlined . instead , in this embodiment , the following set of rules is used for visualizing and selecting manifold regions . 1 . in the selected or node &# 39 ; s visible sub - tree , only the highest - level or nodes are underlined . 2 . in the rest of the tree , only the highest level visible or nodes that are not direct ancestors of the selected node are underlined . 3 . the user can change the current selection by picking an underlined manifold region to select or “ popping up ” to the first ancestor or node of the current selection . these two options are available on the pop - up menu that appears when the author right - clicks in the edit pane . as shown in fig1 , as discussed previously , in the alt version pane , the alternate versions of the currently selected manifold region appear , with the version visible in the edit pane highlighted in yellow 1014 . the user can change the visible version by clicking using an input device on any of the alternate content . in one embodiment , a triangle 1016 is drawn in the left margin to indicate each alternate version . the alt version pane allows the user to perform at least four different operations on the selected manifold regions of alternate content . these are : add version : the “ add version ” operation adds an empty alternate version to the selected or node . a red triangle with no corresponding text is rendered to indicate the newly added version . delete version : the “ delete version ” operation removes the currently highlighted version from the selected or node . the next version in sequential order is highlighted and becomes the visible piece of content . if there are no versions left after the deletion , the or node is removed from the document tree and selection automatically pops back and up one level . copy version : the “ copy version ” operation adds a duplicate of the currently highlighted version to the selected or node . this operation copies the entire sub - tree corresponding to the highlighted version . thus , any nested alternate content is preserved in the new version . copy version special : the “ copy version special ” operation copies the currently highlighted version , but does not preserve its underlying structure . that is , nested manifold regions within the source version are not duplicated . only the content currently visible in the alt version pane is copied and added as a new alternate version . at any given time , the author is always free to edit any piece of text that appears in either pane . in addition , the author can select alternate versions of content by simply clicking on the selection in the alternate - version pane , in which case this version becomes highlighted and also replaces the version currently appearing in the edit pane . in this way , by focusing on the edit pane , the author can get a good sense of how the selected version reads , or appears , alongside the other content in the document , without the distraction of any of its alternate versions . as shown in fig1 , the author can also create new manifold content in the alternate - version pane by selecting text to be configured into multiple versions 1002 and bringing up a pop - up menu 1004 . the author can create new manifold content either by adding a new entry from scratch 1008 or by copying an existing version 1010 . to return to a version of alternate content that contains the selected version , the author can “ pop the selection ” ( one of the menu choices ), or just click outside of the selected version in the edit pane to see all of the highest - level areas 1012 of manifold content again . both of the authoring system ui panes provide standard text editing functionality , with basic formatting operations for selecting font type , font size and style . in addition , the user can specify where in the document to insert image files that are identified by circular icons located in line with the text . backspacing over an icon removes the corresponding image , and to view an image file in a separate window , the author can right - click on an icon and choose view image from the menu . most editing operations in the ui are supported by straight forward transformations of the document tree . in addition to adding , deleting and modifying alternate content for existing manifold regions , the system provides a way to create new manifold regions . creating a new version for an existing region of manifold content is just a matter of adding a new child to the corresponding or node in the document tree . deleting or editing versions of content are similarly straightforward . deleting an existing region of manifold content is just a matter of deleting a child from the corresponding or node in the tree . when editing a region of manifold content the old manifold content is simply replaced with the newly edited content . slightly more complex is the transformation to create a new region of manifold content — the content node containing the selection must be split into three nodes underneath a new and node : the portion to the left of the selected content , a new or node containing a child for the selected region , and the portion to the right of the selected content . the general process of creating a new region of manifold content is shown in fig1 . the selected document content and document tree are input ( process action 1102 ). an attempt is made to find a document sub - tree that can exactly generate the region of selected document content ( process action 1104 ). if the exact sub - tree is not found ( process action 1106 ), a new sub - tree corresponding to the region of selected content is created ( process action 1108 ). once the exact sub - tree corresponding to the selected document content is found or created , a new region of manifold content is created by modifying the document tree so that the sub - tree corresponding to the region of selected content becomes a child of a new or node ( process action 1110 ). this new or node is combined under an and node with the content before the selected content and the content after the selected content . the most complicated operation involves the possible selection of a new region of manifold content that spans several existing manifold content regions — and , in the worst case , intersects them in some arbitrary way . the procedure for creating non - hierarchical manifold content basically involves making a series of recursive transformations on the document tree , “ pushing ” and nodes down through or nodes , in order to transform the tree from its initial representation to an equivalent one in which all of the selected content appears together beneath a single and node . a new or node is then rooted at that spot to accommodate the new alternate content . details of the procedure for modifying the document tree for creating new areas of manifold content are provided in the appendix , section 4 . 1 . with the benefit of manifold content , attractive text and page layout becomes much easier . in this section , the basic adaptive document layout engine is described , focusing particularly on the parts of the approach that are leveraged by manifold content . in the most general sense , as shown in fig1 , the input to the layout procedure is a document tree and a rectangular region , or page , for display . the tree is traversed . as content nodes of different specific types are encountered , calls are made to an appropriate layout engine to determine the size of the panes within a page . once the pane sizes are determined , the portion of the document represented by the content node is rendered in each pane . currently , two types of layout engines are supported in one working embodiment of the adaptive document layout system : a composite - page layout engine , and a simple - page layout engine . it should be noted , however , that various layout engines could be used to execute the various layout tasks . the composite - page layout engine is responsible for the overall structure for the rectangular region it is passed . in other words , it is responsible for determining the pane sizes within a page . specifically , referring to fig1 , the document tree and rectangular region ( page ) available for displaying content are input ( process action 1202 ). the tree is traversed ( process action 1204 ). when a content node is encountered , the node type is determined , a composite layout engine for this node type is called , and the content node that caused this engine to be called designates a set of alternative ways of dividing up the page into panes ( preferably specified via xsl templates ) and provides a collection of named content that is distributed among the different panes ( process actions 1206 , 1208 ). the layout engine chooses among the different layout alternatives according to the dimensions of the rectangular region it is passed and the particular collection of content in the node , as shown in process action 1210 . for instance , if the rectangle is tall and skinny , then the panes might be laid out vertically , whereas if it is short and wide , the engine might choose a horizontal layout instead . once all nodes have been encountered , the simple layout engines for the various pieces of named content are then called recursively in each pane ( process actions 1212 and 1214 ). within a pane , the simple - page layout algorithm is responsible for laying out the various primitive elements like figures and text . the following paragraphs describe how the simple layout engine determines which piece of content to use if there are several versions . this description is followed by a description of a working embodiment of this layout engine . generally , the simple layout engine works as depicted in fig1 . the pane size , alternate versions of content , and attributes of the content to be rendered are input ( process action 1302 ). each version of text content is evaluated to find the best line breaking solution for each version of alternate content , providing a goodness score for each version ( process action 1304 ). additionally , each version of image or figure content is also evaluated to find the best figure placement solution , providing a goodness score for each version of figure placement ( process action 1306 ). the best combinations of alternate versions of text and figure content are then determined using the previously determined goodness scores ( process action 1308 ). optionally , the results for the best combinations can be refined , and the goodness scores can be recomputed ( process action 1310 ). the combination with the best layout goodness score is then rendered in the pane . the general workings of the simple layout engine having been described , the following paragraphs provide additional information on text line - breaking evaluation and figure placement . to format paragraphs of text , a modified form of knuth &# 39 ; s dynamic - programming - based text - formatting algorithm [ 8 ] is used . the original algorithm takes as input a paragraph of text and first determines a set of potential break points b ={ b 1 , b 2 , . . . , b n }. this set includes all inter - word spaces as well as legal hyphenation positions within words . knuth &# 39 ; s algorithm uses dynamic programming to find , in o ( m ) time , the set of breaks bo ⊂ b that results in the best paragraph , as determined by some measure of goodness . for justified text , this measure simply considers how well each line of text fits into the available space . in general , to incorporate alternate versions , additional break points are simply included in b that correspond to the various wordings specified in each or node of the document tree . a small amount of extra bookkeeping is necessary to ensure a solution that does not include conflicting pieces of content ( i . e ., two pieces of content in different child sub - trees of a common or ancestor ). with these modifications , the procedure will find the best line - breaking solution over all choices of content . thus , depending on the size and shape of the region into which the text must flow , the system may choose different versions of content to optimize the line - breaking quality . ( note that the more naive approach of trying all combinations of alternate content results in an algorithm , by contrast , that is exponential in the number of or nodes within the paragraph .) fig1 provides a general depiction of the process actions of the text - breaking algorithm of the invention . the document tree and alternate versions of content are input ( process action 1402 ). the document tree is traversed and breakpoints are recorded for any place that the text could be broken ( e . g ., between words and also between potential hyphenation points within words . ), including additional breakpoints that correspond to the various wordings specified in each or node ( process action 1404 ). as the tree is traversed , information about conflicting breakpoints is recorded ( process action 1406 ). the content up to break point i is referred to as the i - th partial paragraph . starting with the 0 - th and working towards the m - th partial paragraph ( where m is the total number of potential breakpoints found in process action 1404 ), s i , the minimum cumulative badness associated with the sub - problem of breaking the i - th partial paragraph is computed ( process action 1408 ). these scores must be computed in order because the computation for the i - th partial paragraph depends on the scores computed for the 0 - th through ( i − 1 )- th partial paragraphs . for each computed s i , p i , the previous break used to achieve the minimum cumulative badness is also stored ( process action 1410 ). once p m and s m have been computed , the actual set of breaks that achieve the minimum badness for the entire paragraph , s m , are recovered by backtracking through the computed set of previous breaks , starting at p m ( process action 1412 ). to determine the actual text for each line of paragraph , all of the words between the breaks are collected ( process action 1414 ). more detailed information on the text breaking procedure used is provided in the appendix , section 4 . 2 . it should be noted that any conventional text - breaking algorithm can be used for foregoing text breaking procedure in the present adaptive document layout system and method . a simple , brute - force approach , by contrast , is used for selecting among manifold ( floating ) figures and placing them onto the page . for each alternative figure , a score for the approximate “ goodness ” ( or a penalty score ) of the page layout incorporating that figure is computed . in a preferred embodiment , when doing this , an approximate text flow is used in order to make this computation fast , since it may be performed many times to try all combinations . once all combinations have been tried , a more careful metric for the best few combinations can be computed , using the “ optimal ” paragraph text - formatting procedure just described . the metric for measuring the “ goodness ” of a page involves measuring distances between figures and the text that references them , and penalizing figures that do not fall on the same page as their reference . in addition , a score is computed for each for the formatting of each line of text . additional penalties are added for any widows or orphans . there are also parts of the metric that the page designer can tune according to the document &# 39 ; s style — metrics that prefer small or large figures , for example , or figures that together consume a certain proportion of the page . the following paragraphs provide a working embodiment of a layout engine of the adaptive document layout system and method . as discussed previously , adaptive layout documents use a simple xml format , with two new elements added to allow for multiple versions of content : & lt ; or & gt ; elements : these contain the different versions of a piece of content . & lt ; rep & gt ; elements : these contain a single version of content . a number of these are inside an & lt ; or & gt ; element , one for each version of the content . here is an example of two versions of an image , in the representation : the & lt ; rep & gt ; elements may have attributes to indicate which versions are better suited for a particular viewing situation . attributes are added to xml elements by enclosing them inside the element tag : there are a number of attributes an author can use to indicate to the layout engine when it should choose one version of some content over another . for example , the author might want a small , cropped image when a document is displayed on a very small screen , and a larger version of the image when shown on a wide screen . this preference is encoded in the document by using adding attributes to the & lt ; rep & gt ; elements for each of the versions of the image . for the above example , the small image could specify a maximum page width of 400 pixels , which would tell the layout engine that this version is not appropriate for pages over 400 pixels wide . one way this could be expressed using xml format follows ( the meanings of the pagesizebias and pagesizeweight attributes will be explained later ): a complete list of attributes and their meanings for this working embodiment is provided in later paragraphs . when the layout engine is actually placing content on the page , it needs a way to use these attributes to choose one version or another depending on the viewing situation . this is done through a scoring mechanism , where the attributes are evaluated for each version of content , providing a penalty ( or score ) for each . the version with the lowest penalty ( or alternately highest goodness score ) wins , and is placed on the page . generally , a penalty is given to a version of content if the viewing parameters ( e . g . page width ) fall outside of the range given by the & lt ; rep & gt ; element . the penalty usually contains two terms , a constant value as a penalty for falling outside of the legal range at all , as well as a ( weighted ) value proportional to how far outside of the range the parameter is . so , the penalty = weight *( distance outside valid range )+ bias . here , using a simple example at two different page widths , the penalties for each version are computed : & lt ; or & gt ; & lt ; rep maxpagewidth = 400 pagesizebias = 100 pagesizeweight = 1 & gt ; & lt ; img src =” small . jpg ”/& gt ; & lt ;/ rep & gt ; & lt ; rep minpagewidth = 400 pagesizebias = 100 pagesizeweight = 1 & gt ; & lt ; img src =” big . jpg ”/& gt ; & lt ;/ rep & gt ; & lt ;/ or & gt ; if this were being laid out on a page with a width of 800 , it would compute the following scores : rep 2 ( big . jpg ): since the page width isn &# 39 ; t outside of the acceptable bounds , the penalty is 0 if the page width were 300 instead , the penalties would be : rep 1 : 0 rep 2 : 100 * 1 + 100 = 200 2 . 4 . 4 . 3 full list of attributes and scoring for this exemplary working embodiment a complete list of the attributes used for choosing content used in this one working embodiment of the invention is provided in the following tables . the attributes whose names end in “ weight ” or “ bias ” are used to compute the penalties for violating the other attributes . to evaluate the adaptive document layout system and method , some simple manifold - content versions of a real magazine article were used . to simulate viewing on various displays , the article was laid out at different window sizes using the adaptive document layout system and method . fig1 a , 15 b , 15 c show the first article laid out for wide - screen , letter , and pda displays . for comparison , a scan of the original paper document has been included ( see fig1 g ), in addition to the actual web versions of the documents as they appear today ( fig1 d , 15 e and 15 f ). note how the layout engine chooses different content to optimize the layout for the different displays . in the letter - sized display of the article , the layout engine automatically selects a cropped version of the image that appears in the wide - screen layout . in this case , it has been specified in the style sheet for the page a certain desired coverage of the page by images . since the cropped image comes closer to meeting the desired coverage than the original image ( as it would appear if it were scaled to fit on the screen ), the layout algorithm opts for the cropped version . also , note how on the pda - sized display the layout engine automatically chooses a smaller title that also does not include a teaser paragraph . fig1 a - i show some other ways in which the layout engine &# 39 ; s optimization procedure takes advantage of alternate content to prevent typical layout problems . fig1 a and 16b illustrate how alternate content can be used to prevent widows / orphans , common undesirable artifacts . the top image illustrates a viewing situation that results in a widow at the bottom of the second column , and the figure below shows how the layout engine prevents this artifact by displaying an alternate version of the second image . since the presence of widows and orphans results in bad layout scores , the optimizer chooses content that avoids them if at all possible . another frequent layout problem is figure / reference separation — that is , when a figure gets pushed off the page on which a reference to it appears , or vice versa . fig1 c and 16d indicate how multiple representations can be used to avoid this situation . once again , the top image shows the layout that would have been produced without any alternate versions of content , in which the reference to “ fig2 ” has been pushed off the page by the very figure it references — a frustrating predicament that most people working with laying out documents have experienced at one time or another . with an alternate version of the second figure specified in the document , the layout engine succeeds in reuniting the errant reference . fig1 e thorough 16 h demonstrate how the line - breaking algorithm takes advantage of alternate content to produce the best possible results for justified text at different display sizes . for comparison , the results obtained using a version of the paragraph that does not contain alternate content is shown . finally , fig1 i shows one simple benefit of using xsl templates to specify a document &# 39 ; s style . here , a scientific american article is shown laid out using the style parameters of the time example . this appendix includes a section on the details of creating new manifold content regions and the details of the text - breaking algorithm used when creating adaptive documents . the system creates a new region of manifold content by modifying the document tree so that the highlighted content becomes the child of a new or node . the operation can be described more precisely as a two - step process : 1 . the system first tries to identify a sub - tree s that can exactly generate the region of content r highlighted in the edit pane . ( if s satisfies this property it can be said that s corresponds to r , or alternately , that s is an r - corresponding sub - tree .) if no such sub - tree exists , the document tree is transformed validly such that the resulting tree contains a sub - tree that corresponds to r . 2 . once the system has located / created a sub - tree s that corresponds to r , a new or node is inserted above s . the first of these two steps is clearly the more challenging task , and can , in some cases , require a non - trivial tree transformation . in the following section , a general algorithm for performing this operation is described , as well as a simpler approach that places some restrictions on the set of regions that can be converted to have manifold content . at a high level , the algorithm can be described as follows . in the initialization step , a sub - tree s over is identified that contains all of r but may only be able to generate a strict superset of r &# 39 ; s content . it is said that s over may over - approximate r , and s over can be thought of as a conservative estimate of an r - corresponding sub - tree . next , a refinement step is performed that recursively improves s over , stopping once the current estimate corresponds to r . finally a new or node is inserted above the sub - tree . a diagram of this algorithm is shown in fig1 . before describing the details of the algorithm , a convenient assumption is stated about r . without loss of generality it can be assumed that r contains an integral number of content nodes , which is equivalent to saying neither the beginning or end of r bisects a content node . for any r that does not satisfy this property , there exists a simple , valid tree transformation that aligns r with content node boundaries . suppose the beginning of r bisects node n b ; n b can just be replaced with an and node whose first child is a content node containing the portion of n b not in r and whose second child is a content node containing the portion of n b that falls within r . a similar transformation can be made if the end of r bisects a node . thus , only regions that contain an integral number of nodes need be considered . an initial estimate of s over by locating the first common ancestor node n p of all content nodes in r . notice that n p must be an and nodes , since content nodes in different child sub - trees of an or node cannot ( by definition ) appear simultaneously in the edit pane ( and thus , cannot be contained in r ). since the sub - tree s np rooted at n p clearly contains all content nodes in r , it is a conservative estimate of an r - corresponding sub - tree . thus , s over is set equal to n p and a check is made as to whether or not the estimate sub - tree already corresponds exactly to r . if yes , an or node is simply inserted above s over , and the operation is complete . otherwise , refinements ( described below ) are performed until s over is r - corresponding . given s over , the system performs one of two different refinement operations , depending on the properties of the current conservative sub - tree estimate . in particular , all over - approximating can be classified into tow different types that determine which refinement procedure is executed . before describing these two categories , new terminology is introduced . let n p be the root and node of s over and let n ={ n 1 , . . . n m } denote the set of m child sub - trees of n p . since s over is a conservative estimate of an r - corresponding sub - tree , it is known that the content nodes in r are contained within a set of sub - trees n r ⊂ n . notice that since r is a contiguous highlighted region of content , n r must be a contiguous subset of n . for example , if m = 10 , n r might equal { n 4 , . . . , n 8 }, but not { n 4 , n 8 , n 9 ,}. the properties that define a type - 1 over - approximating sub - tree are as follows : 1 . the sub - trees n r correspond exactly to disjoint portions of r that , when assembled , make up all of r &# 39 ; s content . notice that the second property ensures s over is indeed an over - approximation . if n r were equal to n r then ( according to the first property ) s over would already be an r - corresponding sub - tree ! the reason s over does not correspond to r is because there are sub - trees preceding and / or following n r that prevent s over from exactly generating r . instead , s over can only instantiate a piece of content that contains r , with extra text and / or images surrounding the desired content . refining a type - 1 over - approximation is trivial . n r is simply grouped under a new and node p r that is inserted beneath n p at the appropriate position ( fig9 ). due to the first property described above , the sub - tree is rooted at p r is guaranteed to be r - corresponding . thus , the desired manifold region can be created by inserting a new or node above p r . 1 . the sub - trees in n r do not correspond exactly to disjoint portions of r . 2 . n r is a subset ( not necessarily strict ) of n . notice that any s over that does not fall into the first category will satisfy these properties . thus , the types defined here are sufficient to classify all over - approximating sub - trees . the first property here bears further investigation . if | n r |& gt ; 1 , either : 1 ) the first sub - tree in n r does not correspond to the beginning portion of r ; 2 ) the last sub - tree in n r does not correspond to the ending portion of r , or 3 ) both 1 ) and 2 ) apply . note that the sub - trees between the first and last members of n r must correspond exactly to interior portions of r . if | n r |= 1 , then clearly , the one sub - tree in n r cannot correspond to r . these boundary problems arise when r partially overlaps one or more existing manifold regions . specifically , suppose r overlaps the latter portion of m that falls outside of r , and let m overlap be the portion that overlaps r . since it is assumed r is aligned with node boundaries , m contains at least two content nodes — one or more in m outside , and one or more in m overlap . since part of m lies within r , it is known that n m must be located somewhere beneath n p . more specifically , it is known n m must be contained within the first sub - tree ( n first ) in n r . thus , the only instantiation of n first that contains m overlap also includes m outside . in other words , n first does not correspond exactly to the initial portion of r , making s over an over - approximation . an analagous situation arises if the latter portion of r overlaps with the initial portion of an existing manifold region . if s over is a type - 2 approximation , the refinement operations proceed as follows . given the previously stated invariant that the document tree is always alternating , it is known that all child sub - trees in n are either rooted with or nodes or are single content nodes . for convenience , the child sub - trees of these or nodes are referred to as grandchild sub - trees of n p . thus , in the terminology of classical propositonal logic , n p can be thought of as representing an expression in the conjunctive normal form ( cnf ). in this context , the first step in the refinement operation is a conversion from this representation to an equivalent expression in disjunctive normal form ( dnf ). the general form of this transformation can be illustrated using a simple example from logic : basically , this conversion is performed by turning each combination of literals possible under the cnf expression into a conjunct in the dnf expression . mapping this example back to the document tree domain , the parenthesized disjuncts and literals on the left side of the equation correspond respectively to members of n , and grandchild sub - trees of n p . on the right side of the equation , parenthesized conjuncts correspond to new and sub - trees that group together all possible combinations of the literals on the left . thus , in terms of tree manipulations , the transformation involves replacing n p with an or node n ′ p beneath which a set n ′ of and sub - trees is inserted that contain all possible combinations of the grandchild sub - trees . note that some grandchild sub - trees must be duplicated during this transformation . finally , since this modification may result in a non - alternating document tree , a single - pass merge is performed ( as described previously ) to ensure that the tree alternates . after this tree transformation , the new estimate s over is the unique number n ′ that contains all the content nodes in r . a check is then made to see whether or not s over is r - corresponding , and if not , continue refining until it is . so , how does this transformation improve the approximation s over ? put another way , how is it known repeated refinements will eventually lead to an r - corresponding sub - tree ? clearly , if a type - 2 refinement ever leads to a type - 1 over - approximation , it is known the operation will terminate . all that needs to be done is to perform a final type - 1 refinement and the algorithm is done . as a result what ones needs to show is that a series of type - 2 refinements will eventually lead to an r - corresponding sub - tree or a type - 1 over - approximation . by pushing the or nodes at the roots of the n sub - trees up to n ′ p , a type - 2 refinement removes a set of or nodes from s over . thus , repeated transformations will eventually remove all or nodes from the approximation . at the same time , the transformation ensures that the new s over still contains all the content nodes in r . a sub - tree with no or nodes that contains all of r &# 39 ; s content nodes must either be r - corresponding or a type - 1 over - approximation . as a result , the operation is guaranteed to terminate through some sequence of type - 2 and type - 1 refinement . although the algorithm as presented is fully general ( that is , it will handle arbitrary regions r ), type - 2 refinements can result in dramatic modifications of the document tree ( including some duplicated nodes ) that happen without the user &# 39 ; s knowledge . it is feared that these changes to the document &# 39 ; s structure might confuse the author when she creates a new manifold region . as a result , a mechanism has been implemented that checks whether or not the user &# 39 ; s choice of r will require any type - 2 refinements before proceeding with the operation . this is done simply by performing the initialization step and then checking to see if s over is a type - 1 over - approximation . if not , then it is known at least one type - 2 refinement will be necessary , and the system asks the user if she would like the tool to automatically modify r to simplify the operation . this modification involves expanding r so that any boundary problems ( as described above ) are resolved . a simple type - 1 refinement is performed to create a new manifold region . the following paragraphs describe an efficient method for line - breaking a paragraph with multiple versions of text in an optimal way . the present approach extends knuth &# 39 ; s classic dynamic - programming - based line - breaking algorithm to optimize over alternate wordings within the input paragraph . first it is explained how the original algorithm works , before moving on to discuss the modified version . the standard line - breaking problem asks how to break a given paragraph of text into lines in the best possible way , as determined by some measure of goodness . in the following paragraphs , the objective is to create justified text , for which the measure simply considers how well each line fits into the available space . more specifically , the goal is to achieve some specified , optimal inter - word spacing that is neither too small ( resulting in cramped , hard - to - read text ) nor too large ( resulting in sparse , hard - to - read text ). knuth &# 39 ; s original line - breaking paper formulates this problem statement in a more quantitative way , by defining a scoring system that assigns badness values to lines based on how well they fit . in this system , only positive scores are allowed , with smaller badness indicating a better fit . knuth proposed a number of ways to actually compute badness values , each of which can be distinguished by a few specific details . as expected , all of them penalize a line based on how much its inter - word distance deviates from the desired spacing . if the line &# 39 ; s words are too close or too far apart , it receives a larger badness . the reader is referred to knuth &# 39 ; s paper [ 8 ] for more details on this topic . however , for the purposes of this discussion , it is simply assumed that one of these metrics can be used to compute the badness of a given line . thus , the line - breaking problem can be restated quantitatively as follows : given a paragraph of text , break it into lines whose cumulative badness is minimized . the first step of knuth &# 39 ; s algorithm is to determine from the input paragraph a set of potential break points b ={ b 1 , . . . b n }, where b 1 is defined to be the position immediately preceding the first word and b n to be the position immediately following the last word . this set includes all inter - word spaces as well as legal hyphenation positions within words . given b , the objective is now to find the set of breaks bo ⊂ b that minimizes the paragraph &# 39 ; s cumulative badness . although one could perform this task by computing the badness for every possible set of linebreaks and simply picking the best solution , this would clearly be a very inefficient approach . since one would be considering every element in the power set of b , this algorithm would run in exponential time with respect to n . knuth discovered that one can perform this computation more efficiently using dynamic programming . his key observation is that the line - breaking problem obeys the well - known principle of optimality , a prerequisite for any task solvable via dynamic programming techniques . roughly put , any problem that obeys this principle can be decomposed into sub - problems of different sizes , each of which can be solved efficiently given the solutions to all smaller sub - problems . dynamic programming algorithms take advantage of this property by tackling sub - problems in a bottom - up manner , starting with the smallest and ending with the largest ( original ) problem . the line - breaking problem can be decomposed as follows . given input paragraph q , its i - th partial paragraph is defined to be all the text from the beginning of q until break point b i . thus , q &# 39 ; s second partial paragraph contains the first word in the text , and its i - th partial paragraph is just q itself . let lb i denote the subproblem of breaking q &# 39 ; s i - th partial paragraph , noting that is just the original task of dividing q into lines . according to the principle of optimality , it is known that the solution to lb i can be solved efficiently given solutions to lb i through lb i - 1 . thus , knuth &# 39 ; s approach is simply to solve in order , updating the current set of known solutions at each step . given this overview , the specifics of the algorithm are now discussed . as with most dynamic programming techniques , the key implementation detail involves the data structures used to keep track of incremental solutions . for the purposes of knuth &# 39 ; s algorithm , it is useful to define two — s and p . let s be an n - element array whose i - th value s i is the minimum cumulative badness of the solution to lb i , and let p be an n - element array whose i - th value p i indicates the next - to - last break of the solution to lb i , s i and p i are computed as follows : s i = min 1 ≤ j & lt ; i ⁢ ( s j + β ji ) ( 1 ) p i = arg ⁢ ⁢ min 1 ≤ j & lt ; i ⁢ ( s j + β ji ) ( 2 ) where β ji is the badness of the line starting after the j - th break and ending with the i - th break . notice that s i and p i can be calculated in linear time as long as the values s 1 → s i - 1 have already been computed . given these definitions , the algorithm is very simple to describe . using equations 1 - 2 , the elements of s and p can be computed in order . once populated , these data structures contain all the information necessary to reconstruct the optimal break ; s n holds the cumulative badness of the best solution , and by backtracking through p ( starting at p n ), the actual set of breaks b o that achieves this minimum score can be recovered . to determine the actual text for each line of the paragraph , all the words between consecutive breaks in b o are collected . as mentioned above , computing each element of s and p takes at most o ( n ) time . thus , populating these data structures entirely takes o ( n 2 ) time . since the reconstruction step is clearly linear , the time complexity of the entire algorithm is o ( n 2 ), considerably more efficient than the brute force , exponential time algorithm described earlier . in the common case where a paragraph is to be laid out in a region of constant width , knuth proposes a simple , performance - enhancing modification . when s i is computed , it is possible that some of the previous breaks by considered when calculating the minimum value of ( s j + β ji ) are invalid . that is , if the text between b j and b i cannot possibly fit on a single line in the available region ( without over - lapping ), then is an invalid break with respect to b i . the key observation is that a break that is invalid with respect to b i will be invalid for breaks b i + 1 → b n , as well . in other words , if the text between b j and b i cannot fit onto a line , the text between b j and b k , for i & lt ; k ≦ n , cannot possibly fit onto a line either . thus , once a break point becomes invalid , it is no longer necessary to consider it when computing subsequent entries in s and p . in practice , an active set a of all currently valid breaks is maintained . notice that | a | is bounded by w , the maximum number of words that can possibly fit onto a line . at the beginning of the algorithm , a is initialized to ø . when computing each entry s i and p i , only the break points in a are considered : after recording these values , b i is added to a and ( most significantly ) any invalid break points found during the computation are removed . thus , instead of taking time o ( n ) to compute each entry in s and p , it takes time o ( w ). as a result , the entire algorithm now takes o ( nw ), rather than o ( n 2 ) time . since n is ordinarily much larger than w , this represents a significant performance improvement . thus far , the standard line - breaking approach for paragraphs of text has been described . however , for documents with multiple representations of content , the input is in general a paragraph with alternate versions of text — that is , a document tree with or nodes that specify multiple wordings . in this context , the line - breaking problem can be reformulated as follows . given an input paragraph with alternate text , find the optimal way of breaking the paragraph into lines considering all possible textual combinations . one naive way of computing an optimal line - breaking for a paragraph with alternate text would be to enumerate all possible versions of the paragraph ( with all combinations of alternate text ), run knuth &# 39 ; s algorithm on each one and then pick the solution that achieves the best score . however , since there are exponentially many combinations with respect to the number of or nodes in the tree , this approach is highly impractical . in order to find the optimal line - breaking solution efficiently , a modified version of knuth &# 39 ; s method is used . the main idea is to include additional break points in that correspond to the various wordings specified in each or node of the document tree . one then computes s and p as before , maintaining a bit of extra book - keeping to ensure one does not arrive at a solution that includes conflicting pieces of content ( i . e . two pieces of content in different child sub - trees of a common or ancestor ). since b contains potential break points over all different versions of the text , the resulting break b o represents the optimal solution with respect to all alternate content . to determine b , the document tree is traversed , adding the appropriate break points for any visited piece of text . note that two arbitrary breaks b i and b j in b can in general correspond to conflicting pieces of text . as a result , information is recorded about conflicting break points as the tree is traversed . more specifically , for each b i εb , one records c ( b i ), the set of conflicting breaks that precede b i : c ( b i )={ b j : 1 ≦ i , b j conflicts with b i } ( 5 ) after this preliminary step , s and p are computed and b o is reconstructed exactly as in the original algorithm but for two differences . first , c must be taken into account . in particular , when computing s i , one only considers those previous break points b j that do not appear in c ( b i ): second , in determining the badness β ji , one must consider all possible alternate content between breaks b j and b i that do not conflict with b i , recording the combination of content that results in the minimum badness for that line . when building the actual text for the final paragraph from b o , this information is used to ensure that the appropriate text is included in each line . the restrictions imposed in equations 6 - 7 on what break points can appear consecutively prevents the algorithm from finding an invalid solution . at the same time , since b includes break points from all the different pieces of text in the document tree , the final line - breaking solution is optimal with respect to all valid combinations of text . thus , this extended version of knuth &# 39 ; s line - breaking algorithm correctly solves the line - breaking problem for alternate content . furthermore , the use of dynamic programming allows the computation to be performed efficiently . using equations 6 and 7 , it is possible to compute s and p in o ( n 2 ) time . ( note that in this case , n is the total number of breaks associated with all pieces of text in the input document tree . since the reconstruction step is still linear , the total algorithm runs in o ( n 2 ) time as well . as with knuth &# 39 ; s original algorithm , efficiency can be improved by eliminating invalid break points from consideration as one computes s and p . however , the presence of alternate text somewhat complicates this modification . to illustrate the difficulty , let us assume that j & lt ; i and after computing s i , it can be found that that b j is invalid with respect to b i . in contrast to the original algorithm , one cannot necessarily conclude from this fact that b j is invalid with respect to all b k , for i & lt ; k ≦ n . more specifically , for any b k that conflicts with b i , no guarantees can be made that the text between b j and b k does not fit onto a line and therefore , b j must be considered when computing s k and p k . however , for any b k that does not conflict with b i , it is known that b j must be invalid , and can therefore ignore it when computing s k and p k . to handle this complication , one keeps track of which computations first invalidate a particular break point . in particular , i ( b j ) represents the set of breaks responsible for invalidating b j : i ( b j )={ b i : computing s i invalidated b j } ( 8 ) at the beginning of the algorithm , initialize i ( b i )= ø , for all b i εb . then , when computing each entry s i and p i , i is used to exclude the appropriate previous breaks from consideration : α ( i , j )=∃ b k εi ( bj ) s . t . b i does not conflict with b k . ( 11 ) although the notation is somewhat bulky , equations 9 - 11 indicate that the calculation of s i and p i need only consider previous breaks b j that satisfy the following two conditions : a ) b j is a break that precedes b i ( 1 ≦ j & lt ; i ) b ) at least one of the breaks b k responsible for invalidating b j does not conflict with b i (∃ b k εi ( b j ) s . t . b i does not conflict with b k ) if b j is considered in the computation ( i . e . it satisfies these two conditions ) and is invalidated , then b i is added to i ( b j ). as a result of this modification , the algorithm considers the minimum number of previous breaks when calculating each entry in s and p . however , unlike before , it is not possible to bound the computation of s i and p i by w . in the worst case , there may be a large amount of actual text in the document tree ( i . e . n & gt ;& gt ; w ), but every combination of content could fit on a single line . thus , no break point would ever be invalidated while populating p and s . however , equations 9 - 10 decrease the lower bound of the algorithm to ω ( n w ). this running time can clearly be achieved using a degenerate input document tree that contains only one static version of the paragraph text . in contrast , notice that equations 6 - 7 would result in an n 2 computation even with this degenerate input . in practice , it has been observed that significant performance improvements for paragraphs result with several alternate wordings . the foregoing description of the invention has been presented for the purposes of illustration and description . it is not intended to be exhaustive or to limit the invention to the precise form disclosed . many modifications and variations are possible in light of the above teaching . it is intended that the scope of the invention be limited not by this detailed description , but rather by the claims appended hereto . greg badros , alan borning , kim marriott , and peter stuckey . constraint cascading style sheets for the web . in acm user interface software and technology conference proceedings , 1999 . greg badros , jeffrey nichols , and alan borning . scwm — an intelligent constraint - enabled window manager . in aaai smart graphics conference proceedings , 2000 . alan borning , richard lin , and kim marriott . constraints for the web . in acm multimedia conference proceedings , pages 173 - 182 , november 1997 . alan borning , richard lin , and kim marriott . constraint - based document layout for the web . multimedia systems , 8 : 177 - 189 , 2000 . alan borning , kim marriott , peter stuckey , and yi xiao . solving linear arithmetic constraints for user interface applications . in acmuser interface software and technology conference proceedings , pages 87 - 96 , october 1997 . r . furuta , j . schofield , and a . shaw . document formatting systems : survey , concepts and issues . acm computing surveys , pages 417 - 472 , 1982 . r . johari , j . marks , a . partovi , and s . shieber . automatic yellow - pages pagination and layout . technical report , merl , 1996 . donald e . knuth and michael f . plass . breaking paragraphs into lines . software — practice and experience , 11 : 1119 - 1184 , 1981 . hakon wium lie and bert bos . cascading style sheets , level 1 , 1996 . arno j . h . peels , norbert t . m . janssen , and wop nawijn . document architecture and text formatting . acm transactions on information systems , 1985 . louis weitzman and kent wittenburg . automatic presentation of multimedia documents using relational grammars . in acm multimedia conference proceedings , pages 443 - 451 , october 1994 .