Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

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

Introduction
Dynamic
programming
Algorithms
Aesthetics
onlyFrank Mittelbach
frank.mittelbach@latex-project.org
LATEX3 Project

April 29, 2017
(

:

:

)

Time and space
Through the
Looking Glass. . . and what
Alice foundthere“Well, in OUR country,” said
Alice, still panting a little,“you’d generally get tosomewhere else—if you ranvery fast for a long time, as
we’ve been doing.”

Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
onlyJohn Tenniel, 1870

“A slow sort of country!” said
the Queen. “Now, HERE,
you see, it takes all therunning YOU can do, to keepin the same place. If you wantto get somewhere else, youmust run at least twice as fast
as that!”
(

:

:

)

Time and space
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Placing figures on pages (general formula)!

pages + figures − 1
figures=?

Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Placing figures on pages (one per page maximum)!

pages
figures=?

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

:

:

)

Time and space
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Placing figures on pages (general formula)!

pages + figures − 1
figures=?

Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Placing figures on pages (one per page maximum)!

pages
figures=?

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

:

:

)

Time and space
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Placing figures on pages (general formula)!

pages + figures − 1
figures=?

Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Placing figures on pages (one per page maximum)!

pages
figures=?

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

:

:

)

So what now?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Can it be helped a little?
(:
Takayama 2009:)

Defining the problem
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Input model
I A sequence of text blocks T = {t1 , t2 , . . . , tn }I A sequence of (figure) floats F = {f1 , f2 , . . . , f` }I (possibly some more float sequences — ignored for now)

Layout model
I A sequence of spreads S1 , S2 , . . . , Skwith columns/pages (sizes may differ)with areas for floats
I constraints for the filling process
I some further auxiliary information
I
I

(

:

:

)

Defining the problem
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Input model
I A sequence of text blocks T = {t1 , t2 , . . . , tn }I A sequence of (figure) floats F = {f1 , f2 , . . . , f` }I (possibly some more float sequences — ignored for now)

Layout model
I A sequence of spreads S1 , S2 , . . . , Skwith columns/pages (sizes may differ)with areas for floats
I constraints for the filling process
I some further auxiliary information
I
I

(

:

:

)

Defining the problem (continued)
Through the
Looking Glass. . . and what
Alice found
there

Paginations
I A mapping p : T ∪ F → {1, 2, . . . , k} such thatFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms

p(ti ) ≤ p(tj )for 1 ≤ i < j ≤ np(fi ) ≤ p(fj )for 1 ≤ i < j ≤ `I P is the set of all possible paginations of T ∪ F

Aesthetics
only

Objective function (cost function)
I A function Q : P → <Optimization task
I We seek: p0 ∈ P such that Q(p0 ) ≤ Q(p) for all p ∈ P
(

:

:

)

Defining the problem (continued)
Through the
Looking Glass. . . and what
Alice found
there

Paginations
I A mapping p : T ∪ F → {1, 2, . . . , k} such thatFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms

p(ti ) ≤ p(tj )for 1 ≤ i < j ≤ np(fi ) ≤ p(fj )for 1 ≤ i < j ≤ `I P is the set of all possible paginations of T ∪ F

Aesthetics
only

Objective function (cost function)
I A function Q : P → <Optimization task
I We seek: p0 ∈ P such that Q(p0 ) ≤ Q(p) for all p ∈ P
(

:

:

)

Defining the problem (continued)
Through the
Looking Glass. . . and what
Alice found
there

Paginations
I A mapping p : T ∪ F → {1, 2, . . . , k} such thatFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms

p(ti ) ≤ p(tj )for 1 ≤ i < j ≤ np(fi ) ≤ p(fj )for 1 ≤ i < j ≤ `I P is the set of all possible paginations of T ∪ F

Aesthetics
only

Objective function (cost function)
I A function Q : P → <Optimization task
I We seek: p0 ∈ P such that Q(p0 ) ≤ Q(p) for all p ∈ P
(

:

:

)

What can we do?
(Getting requirements for Q)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Example 1: Make a gut decision
I I.e., look at each pagination (for a second) and decide
I Clearly not workable:
I

Introduction
Dynamic
programming

Already for “Through the Looking Glass” that takes
longer than the current age of the universe

Example 2: Base decision on call-out/float distance

Algorithms
Aesthetics
only

I I.e., how many pages do I need to turn to reach a float
I
I

Linear formula: solvable using dynamic programming
Quadratic formula: NP-complete as shown by Plass

Example 3: Recto/verso criteria
I E.g., penalize if call-out and float are on the same type ofpageI

Again NP-complete as shown by Plass
(

:

:

)

What can we do?
(Getting requirements for Q)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Example 1: Make a gut decision
I I.e., look at each pagination (for a second) and decide
I Clearly not workable:
I

Introduction
Dynamic
programming

Already for “Through the Looking Glass” that takes
longer than the current age of the universe

Example 2: Base decision on call-out/float distance

Algorithms
Aesthetics
only

I I.e., how many pages do I need to turn to reach a float
I
I

Linear formula: solvable using dynamic programming
Quadratic formula: NP-complete as shown by Plass

Example 3: Recto/verso criteria
I E.g., penalize if call-out and float are on the same type ofpageI

Again NP-complete as shown by Plass
(

:

:

)

What can we do?
(Getting requirements for Q)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Example 1: Make a gut decision
I I.e., look at each pagination (for a second) and decide
I Clearly not workable:
I

Introduction
Dynamic
programming

Already for “Through the Looking Glass” that takes
longer than the current age of the universe

Example 2: Base decision on call-out/float distance

Algorithms
Aesthetics
only

I I.e., how many pages do I need to turn to reach a float
I
I

Linear formula: solvable using dynamic programming
Quadratic formula: NP-complete as shown by Plass

Example 3: Recto/verso criteria
I E.g., penalize if call-out and float are on the same type ofpageI

Again NP-complete as shown by Plass
(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)

Algorithms
Aesthetics
only

Problem exhibits optimal substructure (optimality principle)
I The tricky bit

(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)

Algorithms
Aesthetics
only

Problem exhibits optimal substructure (optimality principle)
I The tricky bit

(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)
I We denote with P(S ,...,S )i

I
Algorithms
Aesthetics
only

j

a,b
c,d to mean

all paginations of text blocks ta , . . . , tb and figures
fc , . . . , fd onto spreads Si , . . . , Sj

Problem exhibits optimal substructure (optimality principle)
I The tricky bit

(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)
I We denote with P(S ,...,S )
i

I

j

a,b
c,d to mean

all paginations of text blocks ta , . . . , tb and figures
fc , . . . , fd onto spreads Si , . . . , Sj

I Examples:
81,150P(S1 ,S2 ) 1,80
⊂ P(S1 ,...,S4 ) 1,150
1,2 × P(S3 ,S4 ) 3,4
1,4

Problem exhibits optimal substructure (optimality principle)
I The tricky bit
(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)
I We denote with P(S ,...,S )
i

I

j

a,b
c,d to mean

all paginations of text blocks ta , . . . , tb and figures
fc , . . . , fd onto spreads Si , . . . , Sj

I Examples:
81,150P(S1 ,S2 ) 1,80
⊂ P(S1 ,...,S4 ) 1,150
1,2 × P(S3 ,S4 ) 3,4
1,4
111,150
P(S1 ,...,S3 ) 1,110⊂ P(S1 ,...,S4 ) 1,150
1,2 × P(S4 ) 3,4
1,4

Problem exhibits optimal substructure (optimality principle)
I The tricky bit
(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)
I We denote with P(S ,...,S )
i

I

j

a,b
c,d to mean

all paginations of text blocks ta , . . . , tb and figures
fc , . . . , fd onto spreads Si , . . . , Sj

I Examples:
81,150P(S1 ,S2 ) 1,80
⊂ P(S1 ,...,S4 ) 1,150
1,2 × P(S3 ,S4 ) 3,4
1,4
111,150
P(S1 ,...,S3 ) 1,110⊂ P(S1 ,...,S4 ) 1,150
1,2 × P(S4 ) 3,4
1,4
81,110P(S1 ,S2 ) 1,80
⊂ P(S1 ,...,S3 ) 1,110
1,2 × P(S3 ) ∅,∅1,2

Problem exhibits optimal substructure (optimality principle)
I The tricky bit
(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)

Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Problem exhibits optimal substructure (optimality principle)
I The tricky bit
I A problem exhibits optimal substructure if

the optimal solution to the problem incorporates only
optimal solutions to its subproblems;
I the subproblems can be solved independently.
I

(

:

:

)

The dynamic programming methodology
When possible?
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Problem consists of overlapping subproblems
I Clearly, that’s the case (with sensible subproblems)

Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Problem exhibits optimal substructure (optimality principle)
I The tricky bit
I A problem exhibits optimal substructure if

the optimal solution to the problem incorporates only
optimal solutions to its subproblems;
I the subproblems can be solved independently.
I

I Now what does this mean?

(

:

:

)

The dynamic programming methodology
Optimality principle
Through the
Looking Glass. . . and what
Alice found
there

What does it mean?
I Assume we search for p0 with Q(p0 ) minimal andFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms

p0 ∈ P(S1 ,...,S4 ) 1,150
1,4
I Assume further that we find
36,80
81,110p0 ∈ P(S1 ) 1,35
× P(S4 ) 111,150
1,1 × P(S2 ) 2,2 × P(S3 ) ∅,∅3,4

Aesthetics
only. . . then the optimality principle means that
I p0 (suitably restricted) is also an optimal solution forP(S1 ) 1,35
1,1

P(S1 ,S2 ) 1,80
1,2

I and many others, e.g., P(S ,...,S )2

4

P(S1 ,...,S3 ) 1,110
1,2
36,150
etc.
2,4
(

:

:

)

The dynamic programming methodology
Optimality principle
Through the
Looking Glass. . . and what
Alice found
there

What does it mean?
I Assume we search for p0 with Q(p0 ) minimal andFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms

p0 ∈ P(S1 ,...,S4 ) 1,150
1,4
I Assume further that we find
36,80
81,110p0 ∈ P(S1 ) 1,35
× P(S4 ) 111,150
1,1 × P(S2 ) 2,2 × P(S3 ) ∅,∅3,4

Aesthetics
only. . . then the optimality principle means that
I p0 (suitably restricted) is also an optimal solution forP(S1 ) 1,35
1,1

P(S1 ,S2 ) 1,80
1,2

I and many others, e.g., P(S ,...,S )2

4

P(S1 ,...,S3 ) 1,110
1,2
36,150
etc.
2,4
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

If dynamic programming is applicable we canI solve each subproblem only once
I and remember the result

Introduction

I construct the optimal solution of a bigger subproblem

Dynamic
programmingby extending and combining smaller subproblems

Algorithms
Aesthetics
only

Example:I Find the best way to put t1 , . . . , tb and f1 , . . . , fd onto

spreads S1 , . . . , Si :
0

0

1,a
a +1,bP(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c0 × P(Si ) c0 +1,d
..
.
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction

If dynamic programming is applicable we canI solve each subproblem only once
I and remember the result
I construct the optimal solution of a bigger subproblem

by extending and combining smaller subproblems

Dynamic
programming
Algorithms
Aesthetics
only

Example:I Find the best way to put t1 , . . . , tb and f1 , . . . , fd onto

spreads S1 , . . . , Si :P(S1 ,...,Si ) 1,b
1,d
0

0

1,a
a +1,bP(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c0 × P(Si ) c0 +1,d
..
.
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

If dynamic programming is applicable we canI solve each subproblem only once
I and remember the result
I construct the optimal solution of a bigger subproblem

by extending and combining smaller subproblems
Example:I Find the best way to put t1 , . . . , tb and f1 , . . . , fd onto

spreads S1 , . . . , Si :
1,a
a+1,b
P(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c × P(Si ) c+1,d
0

0

1,a
a +1,bP(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c0 × P(Si ) c0 +1,d
..
.
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

If dynamic programming is applicable we canI solve each subproblem only once
I and remember the result
I construct the optimal solution of a bigger subproblem

by extending and combining smaller subproblems
Example:I Find the best way to put t1 , . . . , tb and f1 , . . . , fd onto

spreads S1 , . . . , Si :
1,a
a+1,b
P(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c × P(Si ) c+1,d
0

0

1,a
a +1,bP(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c0 × P(Si ) c0 +1,d
..
.
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

If dynamic programming is applicable we canI solve each subproblem only once
I and remember the result
I construct the optimal solution of a bigger subproblem

by extending and combining smaller subproblems
Example:I Find the best way to put t1 , . . . , tb and f1 , . . . , fd onto

spreads S1 , . . . , Si :
1,a
a+1,b
P(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c × P(Si ) c+1,d
0

0

1,a
a +1,bP(S1 ,...,Si ) 1,b
1,d ⊃ P(S1 ,...,Si−1 ) 1,c0 × P(Si ) c0 +1,d
..
.
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Example continued:
I In other words, we haveP(S1 ,...,Si ) 1,b
1,d =

[

a+1,b
P(S1 ,...,Si−1 ) 1,a1,c × P(Si ) c+1,d

1≤a≤b
1≤c≤d
I So if we know the best way for eachP(S1 ,...,Si−1 ) 1,a1,cthen all we need to do is to calculate all theP(Si ) a+1,bc+1,d
and apply Q to determine the best solution.
(

:

:

)

The dynamic programming methodology
Applying it
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Example continued:
I In other words, we haveP(S1 ,...,Si ) 1,b
1,d =

[

a+1,b
P(S1 ,...,Si−1 ) 1,a1,c × P(Si ) c+1,d

1≤a≤b
1≤c≤d
I So if we know the best way for eachP(S1 ,...,Si−1 ) 1,a1,cthen all we need to do is to calculate all theP(Si ) a+1,bc+1,d
and apply Q to determine the best solution.
(

:

:

)

The dynamic programming methodology
Why does it sometimes fail?
Through the
Looking Glass. . . and what
Alice foundthere

Example continued:
I Suppose we have a pagination p = p0 × p00 withFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
onlyp ∈ P(S1 ,...,Si ) 1,b1,dandp0 ∈ P(S1 ,...,Si−1 ) 1,a1,cp00 ∈ P(Si ) a+1,b
c+1,d

I Then we need to be able to calculate Q(p) from Q(p0 )and Q(p00 )1,a

I For example: Q(p) = Q(p0 ) + Q(p00 ) + Q̃(P(S ,...,S1i−1 ) 1,c)

But for the NP-complete cases this is
I not possible as the “quality” depends on where thecall-out is (within p0 ) in relation to the float (in p00 )I not depending on a fixed value based on P(S ,...,S11,ai−1 ) 1,c
(

:

:

)

The dynamic programming methodology
Why does it sometimes fail?
Through the
Looking Glass. . . and what
Alice foundthere

Example continued:
I Suppose we have a pagination p = p0 × p00 withFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
onlyp ∈ P(S1 ,...,Si ) 1,b1,dandp0 ∈ P(S1 ,...,Si−1 ) 1,a1,cp00 ∈ P(Si ) a+1,b
c+1,d

I Then we need to be able to calculate Q(p) from Q(p0 )and Q(p00 )1,a

I For example: Q(p) = Q(p0 ) + Q(p00 ) + Q̃(P(S ,...,S1i−1 ) 1,c)

But for the NP-complete cases this is
I not possible as the “quality” depends on where thecall-out is (within p0 ) in relation to the float (in p00 )I not depending on a fixed value based on P(S ,...,S11,ai−1 ) 1,c
(

:

:

)

The dynamic programming methodology
Why does it sometimes fail?
Through the
Looking Glass. . . and what
Alice foundthere

Example continued:
I Suppose we have a pagination p = p0 × p00 withFrank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
onlyp ∈ P(S1 ,...,Si ) 1,b1,dandp0 ∈ P(S1 ,...,Si−1 ) 1,a1,cp00 ∈ P(Si ) a+1,b
c+1,d

I Then we need to be able to calculate Q(p) from Q(p0 )and Q(p00 )1,a

I For example: Q(p) = Q(p0 ) + Q(p00 ) + Q̃(P(S ,...,S1i−1 ) 1,c)

But for the NP-complete cases this is
I not possible as the “quality” depends on where thecall-out is (within p0 ) in relation to the float (in p00 )I not depending on a fixed value based on P(S ,...,S11,ai−1 ) 1,c
(

:

:

)

The basic algorithm(no floats)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Start up
I Let A = {a0 , a1 , a2 , . . .} be elements from the text streamthat have been identified as places where we can end a
spread (plus info how we got there)
I Initially this contains just a0 (start of document)

Main loop through all elements t∗ ∈ T
I Check if we can successfully build a spread from one ormore a ∈ A to the current t∗
I For each new spread that ends, check which path gives

the best result (according to Q) and add that one as a
new element to A
I

(here we need the optimality principle)

I Whenever some ai ∈ A is too far away from t∗ (overfull

spread) remove it from A
(

:

:

)

The basic algorithm(no floats)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Start up
I Let A = {a0 , a1 , a2 , . . .} be elements from the text streamthat have been identified as places where we can end a
spread (plus info how we got there)
I Initially this contains just a0 (start of document)

Main loop through all elements t∗ ∈ T
I Check if we can successfully build a spread from one ormore a ∈ A to the current t∗
I For each new spread that ends, check which path gives

the best result (according to Q) and add that one as a
new element to A
I

(here we need the optimality principle)

I Whenever some ai ∈ A is too far away from t∗ (overfull

spread) remove it from A
(

:

:

)

The basic algorithm continued(no floats)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Finishing off
I Eventually, we will reach the end of the document . . .
I . . . then work from the best solution backwards throughall the elements we passed throughI That defines our optimal solution

Complexity
I The outer loop has n elements
I The inner loop is the size of A which isbounded by a constant if all spreads have the samestructure→ O(c · n) = O(n)I otherwise it can be at most n→ O(n2 )
I

(

:

:

)

The basic algorithm continued(no floats)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Finishing off
I Eventually, we will reach the end of the document . . .
I . . . then work from the best solution backwards throughall the elements we passed throughI That defines our optimal solution

Complexity
I The outer loop has n elements
I The inner loop is the size of A which isbounded by a constant if all spreads have the samestructure→ O(c · n) = O(n)I otherwise it can be at most n→ O(n2 )
I

(

:

:

)

The extended algorithm(with floats)
Through the
Looking Glass. . . and what
Alice found
there

When starting up
I Compile info about each call-out

Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

When t∗ is identified as a new endpoint for a spread
I Prepare a list of all possible float placements for the next

spread (conservative)
I Add a new a ∈ A for each of them

When finishing off
I We need to deal with the case of unplaced floats

We can, for example, add them on further spreads(with some extra costs)
I or drop them as “non-solutions”
I

(

:

:

)

The extended algorithm(with floats)
Through the
Looking Glass. . . and what
Alice found
there

When starting up
I Compile info about each call-out

Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

When t∗ is identified as a new endpoint for a spread
I Prepare a list of all possible float placements for the next

spread (conservative)
I Add a new a ∈ A for each of them

When finishing off
I We need to deal with the case of unplaced floats

We can, for example, add them on further spreads(with some extra costs)
I or drop them as “non-solutions”
I

(

:

:

)

The extended algorithm(with floats)
Through the
Looking Glass. . . and what
Alice found
there

When starting up
I Compile info about each call-out

Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

When t∗ is identified as a new endpoint for a spread
I Prepare a list of all possible float placements for the next

spread (conservative)
I Add a new a ∈ A for each of them

When finishing off
I We need to deal with the case of unplaced floats

We can, for example, add them on further spreads(with some extra costs)
I or drop them as “non-solutions”
I

(

:

:

)

The extended algorithm continued(with floats)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction

Complexity
I The outer loop has n elements
I The inner loop is the size of A:
I

The number of elements ending in a different t∗ is either
I

Dynamic
programming
Algorithms

I
I

Aesthetics
only

O(n) for fixed spread structureor O(n2 ) otherwise

For each new t∗ we compile the set of all potentiallypossible float placements for the next spread
I
I

This number is bounded by a constant (available space!)
Any of the available floats might be the first

I ThusI
I

If the spread all have the same structure → O(n · `)otherwise → O(n2 · `)I Floats add a complexity factor in the size of their stream!
(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach

Rule types
I Absolute rule: placement not allowed if violated
I Preference rule: placement is (un)favorable

Introduction
Dynamic
programming
Algorithms

Call-out / float relations
I Floats are placed in order of their first/main call-out
I

Aesthetics
only

Different streams are (usually) independent

I A float must appear after its call-out . . .

same or later column (usual approach)strictly after (fairly restrictive)
I same page or spread or later (difficult with greedy
algorithms; involves reformatting)
I must be placed in their subsection (dangerous)
I must be visible from the call-out (very dangerous)
I
I

(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for placement
I There cannot be more than x floats on a single page
I The top area of a column may receive a maximum of y

floats, the bottom area of z floats
I If more than x% of the space on a column is occupied byfloats then no normal text will appear in that column
I Every column must contain a minimum of x% of text
I All the floats are stacked vertically vertically at the topof a page; alternative: they can appear at the top or
bottom (but not in both places)
I Floats can be horizontally placed if they are visuallycompatible (e.g., have identical heights); might also berequested for floats placed in adjacent columns
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for placement
I There cannot be more than x floats on a single page
I The top area of a column may receive a maximum of y

floats, the bottom area of z floats
I If more than x% of the space on a column is occupied byfloats then no normal text will appear in that column
I Every column must contain a minimum of x% of text
I All the floats are stacked vertically vertically at the topof a page; alternative: they can appear at the top or
bottom (but not in both places)
I Floats can be horizontally placed if they are visuallycompatible (e.g., have identical heights); might also berequested for floats placed in adjacent columns
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for placement
I There cannot be more than x floats on a single page
I The top area of a column may receive a maximum of y

floats, the bottom area of z floats
I If more than x% of the space on a column is occupied byfloats then no normal text will appear in that column
I Every column must contain a minimum of x% of text
I All the floats are stacked vertically vertically at the topof a page; alternative: they can appear at the top or
bottom (but not in both places)
I Floats can be horizontally placed if they are visuallycompatible (e.g., have identical heights); might also berequested for floats placed in adjacent columns
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for placement
I There cannot be more than x floats on a single page
I The top area of a column may receive a maximum of y

floats, the bottom area of z floats
I If more than x% of the space on a column is occupied byfloats then no normal text will appear in that column
I Every column must contain a minimum of x% of text
I All the floats are stacked vertically vertically at the topof a page; alternative: they can appear at the top or
bottom (but not in both places)
I Floats can be horizontally placed if they are visuallycompatible (e.g., have identical heights); might also berequested for floats placed in adjacent columns
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice foundthere

Rules for the inner structure of a float

Frank
Mittelbach

I Position of caption/legend based on float size

Introduction

I Position of caption/legend based on placement

Dynamic
programming

I Float size alterations (cropping of graphics, etc.)

Algorithms
Aesthetics
only

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats
I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!

(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice foundthere

Rules for the inner structure of a float

Frank
Mittelbach

I Position of caption/legend based on float size

Introduction

I Position of caption/legend based on placement

Dynamic
programming

I Float size alterations (cropping of graphics, etc.)

Algorithms
Aesthetics
only

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats
I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!

(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction

Rules for the inner structure of a float
I Position of caption/legend based on float size
I Position of caption/legend based on placement
I Float size alterations (cropping of graphics, etc.)

Dynamic
programming
Algorithms
Aesthetics
only

Pruning (dropping supposedly bad solutions)
I Too many unplaced floatsI

But documents may have many call-outs close by(danger to drop too much)

I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for the inner structure of a float
I Position of caption/legend based on float size
I Position of caption/legend based on placement
I Float size alterations (cropping of graphics, etc.)

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats andx previous columns have no floats allocated
I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!

(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice foundthere

Rules for the inner structure of a float
I Position of caption/legend based on float size

Frank
Mittelbach

I Position of caption/legend based on placement

Introduction

I Float size alterations (cropping of graphics, etc.)

Dynamic
programming
Algorithms
Aesthetics
only

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats andx previous columns have no floats allocatedI

But only if the floats could have placed there(difficult to check)

I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for the inner structure of a float
I Position of caption/legend based on float size
I Position of caption/legend based on placement
I Float size alterations (cropping of graphics, etc.)

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats andx previous columns have no floats allocated
I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!

(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for the inner structure of a float
I Position of caption/legend based on float size
I Position of caption/legend based on placement
I Float size alterations (cropping of graphics, etc.)

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats andx previous columns have no floats allocated
I Distance between call-out and float too large
I

Described this way creates dependencies between
subproblems, thus violate the optimality principle(difficult to implement correctly)

I Other ideas . . .
I

Topic for further research!
(

:

:

)

Float rules (structuring the approach)
Different types of rules, continued
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Rules for the inner structure of a float
I Position of caption/legend based on float size
I Position of caption/legend based on placement
I Float size alterations (cropping of graphics, etc.)

Pruning (dropping supposedly bad solutions)
I Too many unplaced floats andx previous columns have no floats allocated
I Distance between call-out and float too large
I Other ideas . . .
I

Topic for further research!

(

:

:

)

Applying float rules . . .
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Evaluate when deciding next float placement
I Pruning:

Evaluate when adding a call-out to a trial placement
I Call-out constraint rules (absolute):

(

:

:

)

Applying float rules . . .
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

Evaluate when deciding next float placement
I Pruning:Idrop as soon as possible

I Absolute rules (for a spread):Idrop if violated

I Preference rules (for a spread):I

add cost charge

Evaluate when adding a call-out to a trial placement
I Call-out constraint rules (absolute):

(

:

:

)

Applying float rules . . .
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms

Evaluate when deciding next float placement
I Pruning:Idrop as soon as possible

I Absolute rules (for a spread):Idrop if violated

I Preference rules (for a spread):
I

Aesthetics
only

add cost charge

Evaluate when adding a call-out to a trial placement
I Call-out constraint rules (absolute):I

remove a ∈ A if violated

I Call-out constraint rules (preference):I

add cost charge to a ∈ A
(

:

:

)

Designs without call-out constraints(A bit of a horror scenario)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
onlyJohn Tenniel, 1870
(

:

:

)

Designs without call-out constraints(A bit of a horror scenario)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming

What does this mean?
I No rules that favor a certain region (such as low

distance from the call-out)
I The objective function only implements local aesthetics
I Thus the placement of floats mainly affects the quality

through a better or worse fit of the text blocks

Algorithms
Aesthetics
onlyConsequences
I Dynamic programming would still work, as we caninterpret this as the case in whichII

all call-outs are at the beginning of the document
the objective function adds a zero cost for the distancefrom the call-out

I But that means that pruning not really possible(what would be the criteria?)
(

:

:

)

Designs without call-out constraints(A bit of a horror scenario)
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming

What does this mean?
I No rules that favor a certain region (such as low

distance from the call-out)
I The objective function only implements local aesthetics
I Thus the placement of floats mainly affects the quality

through a better or worse fit of the text blocks

Algorithms
Aesthetics
onlyConsequences
I Dynamic programming would still work, as we caninterpret this as the case in whichII

all call-outs are at the beginning of the document
the objective function adds a zero cost for the distancefrom the call-out

I But that means that pruning not really possible(what would be the criteria?)
(

:

:

)

Designs without call-out constraints
Managing the complexity
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction

Just do it externally
I Advantage: fast
I Disadvantage: no interaction with formatting the text

Dynamic
programming
Algorithms
Aesthetics
only

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

(

:

:

)

Designs without call-out constraints
Managing the complexity
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction

Just do it externally
I Advantage: fast
I Disadvantage: no interaction with formatting the text

Dynamic
programming
Algorithms
Aesthetics
only

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

(

:

:

)

Designs without call-out constraints
Managing the complexity
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction

Just do it externally
I Advantage: fast
I Disadvantage: no interaction with formatting the text

Dynamic
programming
Algorithms
Aesthetics
only

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

(

:

:

)

Mischief managed!
Through the
Looking Glass. . . and what
Alice found
there
Frank
Mittelbach
Introduction
Dynamic
programming
Algorithms
Aesthetics
only

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