Through the Looking Glass. . . and what Alice found there
TUG Conference 2017, Bachotek

Frank Mittelbach
frank.mittelbach@latex-project.org
April 29, 2017

Contents

John Tenniel, 1870

1

Introduction

1

2

Dynamic programming

2

3

Algorithms

4

4

Aesthetics only

6

1

From the looking glass story“Well, in OUR country,” said Alice, still panting alittle, “you’d generally get to somewhere else—if
you ran very fast for a long time, as we’ve been
doing.”“A slow sort of country!” said the Queen. “Now,HERE, you see, it takes all the running YOU cando, to keep in the same place. If you want to getsomewhere else, you must run at least twice as
fast as that!”

Time and space

Time and space

Placing figures on pages (general formula)
pages + figures − 1figures=?

Placing figures on pages (one per page maximum)

pages
=?
figures

Examples (assuming 1 second per quality assessment)• 16 pages, 9 figures → 11440 trials → 3.1 hours• 90 pages, 28 figures → 1.548 × 1023 trials
1015 years

1→ 4.91 ×

Defining the problem (continued)

So what now?

Paginations• A mapping p : T ∪ F → {1, 2, . . . , k} such thatp(ti ) ≤ p(tj )for 1 ≤ i < j ≤ np(fi ) ≤ p(fj )for 1 ≤ i < j ≤ `• P is the set of all possible paginations of T ∪ F

Objective function (cost function)• A function Q : P → <Can it be helped a little?
Takayama 2009

Optimization task
• We seek: p0 ∈ P such that Q(p0 ) ≤ Q(p) for all p ∈ P

2

The dynamic programming methodology

What can we do?
(Getting requirements for Q)
Example 1: Make a gut decision

Defining the problem• I.e., look at each pagination (for a second) and decide

Input model• Clearly not workable:– Already for “Through the Looking Glass” thattakes longer than the current age of the universe• A sequence of text blocks T = {t1 , t2 , . . . , tn }• A sequence of (figure) floats F = {f1 , f2 , . . . , f` }• (possibly some more float sequences — ignored fornow)

Example 2: Base decision on call-out/float distance• I.e., how many pages do I need to turn to reach a float– Linear formula: solvable using dynamic programming

Layout model– Quadratic formula: NP-complete as shown byPlass• A sequence of spreads S1 , S2 , . . . , Sk
– with columns/pages (sizes may differ)– with areas for floats

Example 3: Recto/verso criteria– constraints for the filling process• E.g., penalize if call-out and float are on the same typeof page

– some further auxiliary information– Again NP-complete as shown by Plass2

The dynamic programming methodology
When possible?

The dynamic programming methodology
Applying itProblem consists of overlapping subproblems

If dynamic programming is applicable we can• Clearly, that’s the case (with sensible subproblems)•• solve each subproblem only once

We denote with P(Si ,...,Sj ) a,bc,d to mean

• and remember the result– all paginations of text blocks ta , . . . , tb and figures fc , . . . , fd onto spreads Si , . . . , Sj

• construct the optimal solution of a bigger subproblem
by extending and combining smaller subproblems• Examples:
81,150P(S1 ,S2 ) 1,80
⊂ P(S1 ,...,S4 ) 1,150
1,2 × P(S3 ,S4 ) 3,4
1,4Example:

P(S1 ,...,S3 ) 1,110
× P(S4 ) 111,150⊂ P(S1 ,...,S4 ) 1,150
1,23,41,4• Find the best way to put t1 , . . . , tb and f1 , . . . , fd onto
spreads S1 , . . . , Si :1,80
81,110P(S1 ,S2 ) 1,2× P(S3 ) ∅,∅⊂ P(S1 ,...,S3 ) 1,110
1,2P(S1 ,...,Si ) 1,b1,dProblem exhibits optimal substructure (optimality principle)
1,aa+1,bP(S1 ,...,Si ) 1,b1,d ⊃ P(S1 ,...,Si−1 ) 1,c × P(Si ) c+1,d0• The tricky bit

0a +1,b1,aP(S1 ,...,Si ) 1,b1,d ⊃ P(S1 ,...,Si−1 ) 1,c0 × P(Si ) c0 +1,d..
.

• A problem exhibits optimal substructure if– the optimal solution to the problem incorporates
only optimal solutions to its subproblems;– the subproblems can be solved independently.

The dynamic programming methodology
Applying it• Now what does this mean?

Example continued:• In other words, we have[a+1,bP(S1 ,...,Si ) 1,bP(S1 ,...,Si−1 ) 1,a1,c × P(Si ) c+1,d1,d =The dynamic programming methodology
Optimality principle
What does it mean?

1≤a≤b1≤c≤d• Assume we search for p0 with Q(p0 ) minimal and• So if we know the best way for eachp0 ∈ P(S1 ,...,S4 ) 1,150
1,4P(S1 ,...,Si−1 ) 1,a1,c• Assume further that we findthen all we need to do is to calculate all the36,80
p0 ∈ P(S1 ) 1,35
× P(S3 ) 81,110
× P(S4 ) 111,150
3,4
1,1 × P(S2 ) 2,2∅,∅P(Si ) a+1,bc+1,dand apply Q to determine the best solution.

. . . then the optimality principle means that
• p0 (suitably restricted) is also an optimal solution forP(S1 ) 1,35
1,1P(S1 ,S2 ) 1,80
1,2P(S1 ,...,S3 ) 1,110
1,2• and many others, e.g., P(S2 ,...,S4 ) 36,150
etc.
2,43

The dynamic programming methodology
Why does it sometimes fail?

The basic algorithm continued(no floats)

Example continued:

Finishing off000• Suppose we have a pagination p = p × p with• Eventually, we will reach the end of the document . . .

p ∈ P(S1 ,...,Si ) 1,b1,dandp0 ∈ P(S1 ,...,Si−1 ) 1,a1,c• . . . then work from the best solution backwards
through all the elements we passed througha+1,bp00 ∈ P(Si ) c+1,d• Then we need to be able to calculate Q(p) from Q(p0 )and Q(p00 )• That defines our optimal solution• For example: Q(p) = Q(p0 ) + Q(p00 ) + Q̃(P(S1 ,...,Si−1 ) 1,a1,c )Complexity

But for the NP-complete cases this is• The outer loop has n elements• not possible as the “quality” depends on where thecall-out is (within p0 ) in relation to the float (in p00 )• The inner loop is the size of A which is– bounded by a constant if all spreads have thesame structure → O(c · n) = O(n)• not depending on a fixed value based on
P(S1 ,...,Si−1 ) 1,a1,c3– otherwise it can be at most n → O(n2 )The extended algorithm(with floats)

The algorithms

When starting up
The basic algorithm(no floats)• Compile info about each call-out

Start up
When t∗ is identified as a new endpoint for a spread• Let A = {a0 , a1 , a2 , . . .} be elements from the text
stream that have been identified as places where we
can end a spread (plus info how we got there)• Prepare a list of all possible float placements for thenext spread (conservative)• Initially this contains just a0 (start of document)• Add a new a ∈ A for each of themMain loop through all elements t∗ ∈ TWhen finishing off• Check if we can successfully build a spread from one
or more a ∈ A to the current t∗• We need to deal with the case of unplaced floats– We can, for example, add them on furtherspreads (with some extra costs)• For each new spread that ends, check which pathgives the best result (according to Q) and add that one
as a new element to A

– or drop them as “non-solutions”– (here we need the optimality principle)• Whenever some ai ∈ A is too far away from t∗ (overfull spread) remove it from A4

The extended algorithm continued(with floats)

Float rules (structuring the approach)
Different types of rules, continued

Complexity

Rules for placement• The outer loop has n elements• There cannot be more than x floats on a single page

• The inner loop is the size of A:• The top area of a column may receive a maximum of yfloats, the bottom area of z floats– The number of elements ending in a different t∗
is either• If more than x% of the space on a column is occupied
by floats then no normal text will appear in that column∗ O(n) for fixed spread structure∗ or O(n2 ) otherwise– For each new t∗ we compile the set of all potentially possible float placements for the next
spread• Every column must contain a minimum of x% of text
• All the floats are stacked vertically vertically at thetop of a page; alternative: they can appear at the topor bottom (but not in both places)∗ This number is bounded by a constant (available space!)∗ Any of the available floats might be the first• Floats can be horizontally placed if they are visuallycompatible (e.g., have identical heights); might also berequested for floats placed in adjacent columns• Thus– If the spread all have the same structure → O(n · `)– otherwise → O(n2 · `)Float rules (structuring the approach)
Different types of rules, continued• Floats add a complexity factor in the size of theirstream!

Rules for the inner structure of a float
Float rules (structuring the approach)
Different types of rules• Position of caption/legend based on float size
• Position of caption/legend based on placement

Rule types• Float size alterations (cropping of graphics, etc.)• Absolute rule: placement not allowed if violated
Pruning (dropping supposedly bad solutions)• Preference rule: placement is (un)favorable• Too many unplaced floats and x previous columns
have no floats allocatedCall-out / float relations– But documents may have many call-outs close by(danger to drop too much) But only if the floats
could have placed there (difficult to check)• Floats are placed in order of their first/main call-out– Different streams are (usually) independent• Distance between call-out and float too large• A float must appear after its call-out . . .

– Described this way creates dependencies between subproblems, thus violate the optimality
principle (difficult to implement correctly)– same or later column (usual approach)– strictly after (fairly restrictive)– same page or spread or later (difficult withgreedy algorithms; involves reformatting)• Other ideas . . .

– must be placed in their subsection (dangerous)– Topic for further research!

– must be visible from the call-out (very dangerous)

5Applying float rules . . .

Designs without call-out constraints(A bit of a horror scenario)

Evaluate when deciding next float placement

What does this mean?
• Pruning:• No rules that favor a certain region (such as low distance from the call-out)– drop as soon as possible• Absolute rules (for a spread):• The objective function only implements local aesthetics– drop if violated• Thus the placement of floats mainly affects the quality
through a better or worse fit of the text blocks• Preference rules (for a spread):– add cost charge

Consequences
Evaluate when adding a call-out to a trial placement• Dynamic programming would still work, as we caninterpret this as the case in which• Call-out constraint rules (absolute):– remove a ∈ A if violated– all call-outs are at the beginning of the document• Call-out constraint rules (preference):– the objective function adds a zero cost for thedistance from the call-out– add cost charge to a ∈ A4

• But that means that pruning not really possible (whatwould be the criteria?)

Aesthetics onlyDesigns without call-out constraints
Managing the complexity
Just do it externally

Designs without call-out constraints(A bit of a horror scenario)• Advantage: fast
• Disadvantage: no interaction with formatting the text

Guiding the placement• Advantage: interaction with text placement (whilestill fairly fast)• Disadvantage: difficult to control• More research necessary!

John Tenniel, 1870

6

Mischief managed!

Hope I was able to reveal something new for you.
Thanks all around!
John Tenniel, 1870

7