Computational Intelligence, Volume ??, Number 000, 2017

A General LuaTEX Framework for Globally Optimized Pagination
F RANK M ITTELBACHLATEX3 Project, Mainz, Germany
frank.mittelbach@latex-project.org

Pagination problems deal with questions around transforming a source text stream into a formatted document
by dividing it up into individual columns and pages, including adding auxiliary elements that have some relationshipto the source stream data but may allow a certain amount of variation in placement (such as figures or footnotes).
Traditionally the pagination problem has been approached by separating it into one of micro-typography (e.g.,
breaking text into paragraphs, also known as h&j) and one of macro-typography (e.g., taking a galley of alreadyformatted paragraphs and breaking them into columns and pages) without much interaction between the two.
While early solutions for both problem areas used simple greedy algorithms, Knuth and Plass (1981) introducedin the ’80s a global-fit algorithm for line breaking that optimizes the breaks across the whole paragraph. Thisalgorithm was implemented in TEX’82 (see Knuth (986b)) and has since kept its crown as the best available solution
for this space. However, for macro-typography there has been no (successful) attempt to provide globally optimized
page layout: All systems to date (including TEX) use greedy algorithms for pagination. Various problems in this area
have been researched and the literature documents some prototype development. But none of them have been madewidely available to the research community or ever made it into a generally usable and publicly available system.
This paper is an extended version of the work by Mittelbach (2016) originally presented at the DocEng ’16
conference in Vienna. It presents a framework for a global-fit algorithm for page breaking based on the ideas of
Knuth/Plass. It is implemented in such a way that it is directly usable without additional executables with any modern
TEX installation. It therefore can serve as a test bed for future experiments and extensions in this space. At the sametime a cleaned-up version of the current prototype has the potential to become a production tool for the huge number
of TEX users world-wide.
The paper also discusses two already implemented extensions that increase the flexibility of the pagination
process (a necessary prerequisite for successful global optimization): the ability to automatically consider existingflexibility in paragraph length (by considering paragraph variations with different numbers of lines) and the conceptof running the columns on a double spread a line long or short. It concludes with a discussion of the overall approach,its inherent limitations and directions for future research.
Key words: typesetting; macro-typography; pagination; page breaking; global optimization; automaticlayout; adaptive layout

1. INTRODUCTION
Pagination is the act of transforming a source document into a sequence of columns andpages, possibly including auxiliary elements such as floats (e.g., figures and tables).
As textual material is typically read in sequential order, its arrangement into columns
and pages needs to preserve the sequential property. There are applications where this is not
the case or not fully the case, e.g., in newspaper layout, where stories may be interrupted
and “continued on page X”, but in this paper we limit ourselves to formatting tasks with asingle textual output stream (see Hailpern et al. (2014) for a discussion of problems related tointerrupted texts).
An algorithm that undertakes the task of automatic pagination therefore has to transformthe textual material into individual blocks that form the material for each column and arrange
for distributing auxiliary material across all pages (thereby reducing available column heights)
in a way that it best fulfills a number of (usually) conflicting goals.
This transformation is typically done as a two-step process by first breaking the text
into lines forming paragraphs and this way assembling a galley (known as hyphenation andjustification or h&j for short) and then as a second step by splitting this galley into individualcolumns to form the pages.
© 2017 The Authors. Journal Compilation © 2017 Wiley Periodicals, Inc.

2

C OMPUTATIONAL I NTELLIGENCE

However, separating line breaking and page breaking means that one loses possible
benefits from having both steps influence each other. So it is not surprising that this has been
an area of research throughout the years, e.g., Mittelbach and Rowley (1992); Holkner (2006);
Ciancarini et al. (2012); Piccoli et al. (2012); Hassan and Hunter (2015). The algorithm
outlined in this paper implements some limited interaction to add flexibility to the pagebreaking phase.
The remainder of the paper is structured as follows: We first discuss general questions
related to pagination, give a short overview about attempts to automate that process and thepossible limitation when using a global optimization strategy for pagination. Section 2 thendescribes our framework for implementing globally optimizing pagination algorithms using a
TEX/LuaTEX environment. In Section 3 we have a general look at approaching the problem
using dynamic programming and discuss various useful customizable constraints that can beused to influence this optimization problem. Section 4 then discusses details of the algorithms
we used and gives some computational examples. The paper concludes with an evaluation of
the algorithm quality and an outline of possible further research work.
Although attempts are made to introduce all necessary concepts, the paper assumes acertain level of familiarity with TEX; if necessary refer to Knuth (986a) for an introduction.

1.1. Pagination rules
Rules for pagination and their relative weight in influencing the final result vary fromapplication to application, as they are often (at least to some extent) of an aesthetic nature,
but also because, depending on the given job, some primary goals may outweigh any other. It
is therefore important that any algorithm for this space is configurable to support different
rule sets and able to adjust the weight of each rule in contributing to the final solution.
The primary goal of nearly every document is to convey information to its audience andthus an undisputed “meta” goal for document formatting is to enhance the information flow
or at least avoid hindering or preventing successful communication of information to therecipient. An example of a rule derived from this maxim is the already mentioned requirementof keeping the text flow in clearly understandable reading order.
Other examples are rules regarding float placement: To avoid requiring the reader tounnecessarily flip pages, floating objects should preferably be placed close to (and visiblefrom) their main call-out and if that is not possible they should be placed nearby on later
pages (so that a reader has a clear idea where to search for them). For the same reason theyshould be kept in the order of their main call-outs—though that, for example, is a rule that issometimes broken when placement rules are mainly guided by aesthetic consideration.
Other rules are more aesthetic in nature, even though they too originate from the attempt
to provide easy access to information, as violating them will disrupt the reading flow to someextent: have a heading always followed by a minimal number of lines of normal text, avoid
widows and orphans (end or beginning line of a paragraph on its own at a column break)or do not break at a hyphenated line. An example from mathematical typesetting is to shunsetting displayed equations at the top of a column, the reason being that the text before such aformula is usually an introduction to it, so to aid comprehension they should be keep together
if possible.
Rules like the above have in common that they all reduce the number of allowed places
where a column break could be taken, i.e., they all generate unbreakable larger vertical blocks
in the galley. Thus finding suitable places to cut up the galley into columns of predefinedsizes becomes harder and greedy algorithms nearly always run into stumbling blocks (no pun
intended) where the only path they can take is to move the offending block to the next column,
thereby leaving a possibly large amount of white space on the previous one.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

3

The second major “meta” goal, especially in publishing, is to make best use of theavailable space in order to keep the costs low. If we look only at formatting a single text
stream (no floats) then it is easy to see that this goal stands in direct competition with any
rule derived from the first meta goal. It is easy to prove that a greedy algorithm will always
produce the shortest formatting1 if the column sizes are fixed and all document elements areof fixed size and need to be laid out in sequential order. So in order to satisfy both goals one
needs to allow for either• variations in column heights,• variations in the height of textual elements, or• allow non-sequential ordering of elements.
In this paper we look in particular at the first two options. The last bullet is usually not
an option for text elements, except in the case of documents with short unrelated stories
that can be reordered or texts that are allowed to be split and “continued”. As these form
their own class of documents with their own intrinsic formatting requirements they are notaddressed in this paper (see, for example, Hurlburt (1978); Harrower (1991); Enlund (1991);
Gange et al. (2012)). There is, however, also the possibility to introduce a certain amountof additional flexibility through clever placement of floats (such as figures or tables) as thiswill change the height of individual columns. We do not address the question of optimization
through float placement as part of this paper but assume that floats are either absent or theirplacement predetermined or externally determined. The class of documents for which this canbe assumed is rather large, so the findings in this paper are relevant even with this restriction
in force. Mittelbach (2017) discusses the effects of adding float streams to the optimization
process and the resulting changes in complexity.
A variation in column height (typically by allowing the height to deviate by one line oftext) is a standard trick in craft typography to work around difficult pagination situations. To
hide such a change from the eye of the reader, or at least lessen the impact, all columns of apage and, in two-sided printing, a double spread (facing pages in the output document) need
the same treatment.2 It is also best to only gradually change the column heights to avoid big
differences between one double spread and the next.
The second option involves interaction between the micro- (line breaking of paragraphs,
formatting of inline figures etc.) and the macro-typography phase (pagination of the galley
material), either by dynamically requesting micro-typography variants during pagination orby precompiling them for additional flexibility in the the macro-typography phase. Examples
are line breaking with sub-optimal spacing (variant looseness setting in TEX’s algorithm, e.g.,
Knuth (986a); Hassan and Hunter (2015)) or font compression/expansion (hz-algorithm as
implemented by Hàn Thê´ Thành (2000)) within defined limits. Other examples are figures ortables that can be formatted to different sizes.
1.2. Typical problems during pagination
Problems with pagination are commonplace if a greedy algorithm is used. As a typicalexample Figure 1 shows the first 6 double spreads from “Alice in Wonderland” as it would betypeset by the (greedy) algorithm of LATEX when orphans and widows are disallowed. Mostof the resulting defects can easily be spotted even in the thumbnail presentation. The mostglaring one is on page 7 which ends up being largely empty.
1 The formatting is “shortest” in the sense that compared to any other pagination it will have a lower or equal number ofcolumns/pages and if equal the last column will contain a lesser or equal amount of material.
2 Also the paper for printing should be thick enough, so that the text block on the back is not shining through, as that would bea dead giveaway.

4

C OMPUTATIONAL I NTELLIGENCE—
ALICE’S ADVENTURES IN WONDERLAND
Lewis Carroll
THE MILLENNIUM FULCRUM EDITION 3.0

12

out what she was coming to, but it was too dark to
see anything; then she looked at the sides of the well,and noticed that they were filled with cupboards andbook-shelves; here and there she saw maps and pictures hung upon pegs. She took down a jar fromone of the shelves as she passed; it was labelled ’ORANGE MARMALADE’, but to her great disappointment it was empty: she did not like to drop the jar
for fear of killing somebody, so managed to put it into
one of the cupboards as she fell past it.
’Well!’ thought Alice to herself, ’after such a fallas this, I shall think nothing of tumbling down stairs!
How brave they’ll all think me at home! Why, I
wouldn’t say anything about it, even if I fell off the
top of the house!’ (Which was very likely true.)
Down, down, down. Would the fall NEVER cometo an end! ’I wonder how many miles I’ve fallen by
this time?’ she said aloud. ’I must be getting somewhere near the centre of the earth. Let me see: thatwould be four thousand miles down, I think–’ (for,you see, Alice had learnt several things of this sort in
her lessons in the schoolroom, and though this was
not a VERY good opportunity for showing off her
knowledge, as there was no one to listen to her, still
it was good practice to say it over) ’–yes, that’s about
the right distance–but then I wonder what Latitude
or Longitude I’ve got to?’ (Alice had no idea what
Latitude was, or Longitude either, but thought they
were nice grand words to say.)Presently she began again. ’I wonder if I shall fallright THROUGH the earth! How funny it’ll seemto come out among the people that walk with theirheads downward! The Antipathies, I think–’ (she wasrather glad there WAS no one listening, this time, as
it didn’t sound at all the right word) ’–but I shallhave to ask them what the name of the country is,
you know. Please, Ma’am, is this New Zealand orAustralia?’ (and she tried to curtsey as she spoke–
fancy CURTSEYING as you’re falling through theair! Do you think you could manage it?) ’And what
an ignorant little girl she’ll think me for asking! No,
it’ll never do to ask: perhaps I shall see it written up
somewhere.’Down, down, down. There was nothing else to do,
so Alice soon began talking again. ’Dinah’ll miss mevery much to-night, I should think!’ (Dinah was the

I. Down the Rabbit-HoleAlice was beginning to get very tired of sitting by
her sister on the bank, and of having nothing to do:
once or twice she had peeped into the book her sister
was reading, but it had no pictures or conversationsin it, ’and what is the use of a book,’ thought Alice’without pictures or conversations?’
So she was considering in her own mind (as well as
she could, for the hot day made her feel very sleepy
and stupid), whether the pleasure of making a daisychain would be worth the trouble of getting up andpicking the daisies, when suddenly a White Rabbit
with pink eyes ran close by her.
There was nothing so VERY remarkable in that;nor did Alice think it so VERY much out of the way
to hear the Rabbit say to itself, ’Oh dear! Oh dear! I
shall be late!’ (when she thought it over afterwards,
it occurred to her that she ought to have wondered at
this, but at the time it all seemed quite natural); butwhen the Rabbit actually TOOK A WATCH OUT
OF ITS WAISTCOAT-POCKET, and looked at it,
and then hurried on, Alice started to her feet, for it
flashed across her mind that she had never before seen
a rabbit with either a waistcoat-pocket, or a watch
to take out of it, and burning with curiosity, she ran
across the field after it, and fortunately was just intime to see it pop down a large rabbit-hole under thehedge.
In another moment down went Alice after it, neveronce considering how in the world she was to get out
again.
The rabbit-hole went straight on like a tunnel forsome way, and then dipped suddenly down, so suddenly that Alice had not a moment to think about
stopping herself before she found herself falling downa very deep well.
Either the well was very deep, or she fell very
slowly, for she had plenty of time as she went down
to look about her and to wonder what was going tohappen next. First, she tried to look down and make—cat.) ’I hope they’ll remember her saucer of milk at
tea-time. Dinah my dear! I wish you were down herewith me! There are no mice in the air, I’m afraid, but
you might catch a bat, and that’s very like a mouse,
you know. But do cats eat bats, I wonder?’ And here
Alice began to get rather sleepy, and went on saying
to herself, in a dreamy sort of way, ’Do cats eat bats?
Do cats eat bats?’ and sometimes, ’Do bats eat cats?’
for, you see, as she couldn’t answer either question,
it didn’t much matter which way she put it. She feltthat she was dozing off, and had just begun to dreamthat she was walking hand in hand with Dinah, andsaying to her very earnestly, ’Now, Dinah, tell me
the truth: did you ever eat a bat?’ when suddenly,
thump! thump! down she came upon a heap of sticks
and dry leaves, and the fall was over.
Alice was not a bit hurt, and she jumped up on
to her feet in a moment: she looked up, but it was
all dark overhead; before her was another long passage, and the White Rabbit was still in sight, hurrying down it. There was not a moment to be lost:away went Alice like the wind, and was just in timeto hear it say, as it turned a corner, ’Oh my ears andwhiskers, how late it’s getting!’ She was close behind
it when she turned the corner, but the Rabbit was
no longer to be seen: she found herself in a long, lowhall, which was lit up by a row of lamps hanging fromthe roof.
There were doors all round the hall, but they were
all locked; and when Alice had been all the way down
one side and up the other, trying every door, shewalked sadly down the middle, wondering how she
was ever to get out again.
Suddenly she came upon a little three-legged table,
all made of solid glass; there was nothing on it except
a tiny golden key, and Alice’s first thought was thatit might belong to one of the doors of the hall; but,alas! either the locks were too large, or the key was
too small, but at any rate it would not open any ofthem. However, on the second time round, she cameupon a low curtain she had not noticed before, andbehind it was a little door about fifteen inches high:she tried the little golden key in the lock, and to her
great delight it fitted!
Alice opened the door and found that it led into asmall passage, not much larger than a rat-hole: she

(1)
4

—
’You ought to be ashamed of yourself,’ said Alice,’a great girl like you,’ (she might well say this), ’to
go on crying in this way! Stop this moment, I tellyou!’ But she went on all the same, shedding gallons
of tears, until there was a large pool all round her,about four inches deep and reaching half down thehall.
After a time she heard a little pattering of feetin the distance, and she hastily dried her eyes to see
what was coming. It was the White Rabbit returning,splendidly dressed, with a pair of white kid gloves
in one hand and a large fan in the other: he cametrotting along in a great hurry, muttering to himself
as he came, ’Oh! the Duchess, the Duchess! Oh!
won’t she be savage if I’ve kept her waiting!’ Alice
felt so desperate that she was ready to ask help of any
one; so, when the Rabbit came near her, she began,in a low, timid voice, ’If you please, sir–’ The Rabbit
started violently, dropped the white kid gloves andthe fan, and skurried away into the darkness as hard
as he could go.
Alice took up the fan and gloves, and, as the hall
was very hot, she kept fanning herself all the time she
went on talking: ’Dear, dear! How queer everythingis to-day! And yesterday things went on just as usual.
I wonder if I’ve been changed in the night? Let me
think: was I the same when I got up this morning? I
almost think I can remember feeling a little different.
But if I’m not the same, the next question is, Who in
the world am I? Ah, THAT’S the great puzzle!’ And
she began thinking over all the children she knewthat were of the same age as herself, to see if she
could have been changed for any of them.
’I’m sure I’m not Ada,’ she said, ’for her hair goesin such long ringlets, and mine doesn’t go in ringlets
at all; and I’m sure I can’t be Mabel, for I know
all sorts of things, and she, oh! she knows such avery little! Besides, SHE’S she, and I’m I, and–ohdear, how puzzling it all is! I’ll try if I know all
the things I used to know. Let me see: four times
five is twelve, and four times six is thirteen, and fourtimes seven is–oh dear! I shall never get to twenty atthat rate! However, the Multiplication Table doesn’t
signify: let’s try Geography. London is the capital of
Paris, and Paris is the capital of Rome, and Rome–no, THAT’S all wrong, I’m certain! I must have been—changed for Mabel! I’ll try and say "How doth thelittle–"’ and she crossed her hands on her lap as if shewere saying lessons, and began to repeat it, but her
voice sounded hoarse and strange, and the words did
not come the same as they used to do:–’How doth the little crocodile
Improve his shining tail,And pour the waters of the Nile
On every golden scale!
’How cheerfully he seems to grin,
How neatly spread his claws,
And welcome little fishes inWith gently smiling jaws!’’I’m sure those are not the right words,’ said poor
Alice, and her eyes filled with tears again as she went
on, ’I must be Mabel after all, and I shall have to go
and live in that poky little house, and have next to
no toys to play with, and oh! ever so many lessons tolearn! No, I’ve made up my mind about it; if I’m Mabel, I’ll stay down here! It’ll be no use their putting
their heads down and saying "Come up again, dear!"
I shall only look up and say "Who am I then? Tellme that first, and then, if I like being that person, I’ll
come up: if not, I’ll stay down here till I’m somebody
else"–but, oh dear!’ cried Alice, with a sudden burstof tears, ’I do wish they WOULD put their heads
down! I am so VERY tired of being all alone here!’
As she said this she looked down at her hands, andwas surprised to see that she had put on one of the
Rabbit’s little white kid gloves while she was talking.
’How CAN I have done that?’ she thought. ’I must
be growing small again.’ She got up and went to
the table to measure herself by it, and found that, as
nearly as she could guess, she was now about two feethigh, and was going on shrinking rapidly: she soon
found out that the cause of this was the fan she washolding, and she dropped it hastily, just in time to
avoid shrinking away altogether.
’That WAS a narrow escape!’ said Alice, a gooddeal frightened at the sudden change, but very glad tofind herself still in existence; ’and now for the garden!’and she ran with all speed back to the little door:
but, alas! the little door was shut again, and the little
golden key was lying on the glass table as before, ’andthings are worse than ever,’ thought the poor child,(4)
8’for I never was so small as this before, never! And I
declare it’s too bad, that it is!’As she said these words her foot slipped, and inanother moment, splash! she was up to her chin insalt water. Her first idea was that she had somehow fallen into the sea, ’and in that case I can goback by railway,’ she said to herself. (Alice had been
to the seaside once in her life, and had come to thegeneral conclusion, that wherever you go to on the
English coast you find a number of bathing machines
in the sea, some children digging in the sand withwooden spades, then a row of lodging houses, andbehind them a railway station.) However, she soon
made out that she was in the pool of tears which she
had wept when she was nine feet high.
’I wish I hadn’t cried so much!’ said Alice, as she
swam about, trying to find her way out. ’I shall bepunished for it now, I suppose, by being drowned in
my own tears! That WILL be a queer thing, to be
sure! However, everything is queer to-day.’Just then she heard something splashing about inthe pool a little way off, and she swam nearer tomake out what it was: at first she thought it must bea walrus or hippopotamus, but then she remembered
how small she was now, and she soon made out that
it was only a mouse that had slipped in like herself.
’Would it be of any use, now,’ thought Alice, ’to
speak to this mouse? Everything is so out-of-theway down here, that I should think very likely it can
talk: at any rate, there’s no harm in trying.’ So shebegan: ’O Mouse, do you know the way out of thispool? I am very tired of swimming about here, O
Mouse!’ (Alice thought this must be the right wayof speaking to a mouse: she had never done such athing before, but she remembered having seen in her
brother’s Latin Grammar, ’A mouse–of a mouse–toa mouse–a mouse–O mouse!’) The Mouse looked ather rather inquisitively, and seemed to her to wink
with one of its little eyes, but it said nothing.
’Perhaps it doesn’t understand English,’ thought
Alice; ’I daresay it’s a French mouse, come over with
William the Conqueror.’ (For, with all her knowledgeof history, Alice had no very clear notion how long
ago anything had happened.) So she began again:’Ou est ma chatte?’ which was the first sentence inher French lesson-book. The Mouse gave a sudden

6

leap out of the water, and seemed to quiver all overwith fright. ’Oh, I beg your pardon!’ cried Alicehastily, afraid that she had hurt the poor animal’s
feelings. ’I quite forgot you didn’t like cats.’’Not like cats!’ cried the Mouse, in a shrill, passionate voice. ’Would YOU like cats if you were me?’’Well, perhaps not,’ said Alice in a soothing tone:’don’t be angry about it. And yet I wish I could
show you our cat Dinah: I think you’d take a fancy
to cats if you could only see her. She is such a dear
quiet thing,’ Alice went on, half to herself, as she
swam lazily about in the pool, ’and she sits purringso nicely by the fire, licking her paws and washingher face–and she is such a nice soft thing to nurse–and she’s such a capital one for catching mice–oh, I
beg your pardon!’ cried Alice again, for this time theMouse was bristling all over, and she felt certain it
must be really offended. ’We won’t talk about her
any more if you’d rather not.’’We indeed!’ cried the Mouse, who was trembling
down to the end of his tail. ’As if I would talk onsuch a subject! Our family always HATED cats:
nasty, low, vulgar things! Don’t let me hear the nameagain!’’I won’t indeed!’ said Alice, in a great hurry tochange the subject of conversation. ’Are you–are
you fond–of–of dogs?’ The Mouse did not answer,
so Alice went on eagerly: ’There is such a nice little dog near our house I should like to show you!
A little bright-eyed terrier, you know, with oh, suchlong curly brown hair! And it’ll fetch things when
you throw them, and it’ll sit up and beg for its dinner, and all sorts of things–I can’t remember half ofthem–and it belongs to a farmer, you know, and hesays it’s so useful, it’s worth a hundred pounds! He
says it kills all the rats and–oh dear!’ cried Alice ina sorrowful tone, ’I’m afraid I’ve offended it again!’
For the Mouse was swimming away from her as hard
as it could go, and making quite a commotion in thepool as it went.
So she called softly after it, ’Mouse dear! Do comeback again, and we won’t talk about cats or dogs
either, if you don’t like them!’ When the Mouse heard
this, it turned round and swam slowly back to her:its face was quite pale (with passion, Alice thought),
and it said in a low trembling voice, ’Let us get to

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*

III. A Caucus-Race and aLong Tale
They were indeed a queer-looking party that assembled on the bank–the birds with draggled feathers,
the animals with their fur clinging close to them, andall dripping wet, cross, and uncomfortable.
The first question of course was, how to get dry
again: they had a consultation about this, and aftera few minutes it seemed quite natural to Alice tofind herself talking familiarly with them, as if she
had known them all her life. Indeed, she had quite
a long argument with the Lory, who at last turned
sulky, and would only say, ’I am older than you, andmust know better’; and this Alice would not allow
without knowing how old it was, and, as the Lory
positively refused to tell its age, there was no more
to be said.
At last the Mouse, who seemed to be a personof authority among them, called out, ’Sit down, allof you, and listen to me! I’LL soon make you dry
enough!’ They all sat down at once, in a large ring,with the Mouse in the middle. Alice kept her eyes
anxiously fixed on it, for she felt sure she would catcha bad cold if she did not get dry very soon.
’Ahem!’ said the Mouse with an important air,’are you all ready? This is the driest thing I know.
Silence all round, if you please! "William the Conqueror, whose cause was favoured by the pope, wassoon submitted to by the English, who wanted leaders, and had been of late much accustomed to usurpation and conquest. Edwin and Morcar, the earls ofMercia and Northumbria–"’’Ugh!’ said the Lory, with a shiver.

—

9

10

*

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*

II. The Pool of Tears’Curiouser and curiouser!’ cried Alice (she was somuch surprised, that for the moment she quite forgot
how to speak good English); ’now I’m opening out
like the largest telescope that ever was! Good-bye,feet!’ (for when she looked down at her feet, they
seemed to be almost out of sight, they were getting
so far off). ’Oh, my poor little feet, I wonder who will
put on your shoes and stockings for you now, dears?
I’m sure I shan’t be able! I shall be a great deal too
far off to trouble myself about you: you must manage
the best way you can;–but I must be kind to them,’
thought Alice, ’or perhaps they won’t walk the way I
want to go! Let me see: I’ll give them a new pair ofboots every Christmas.’
And she went on planning to herself how she
would manage it. ’They must go by the carrier,’ shethought; ’and how funny it’ll seem, sending presents
to one’s own feet! And how odd the directions will
look!
ALICE’S RIGHT FOOT, ESQ.
HEARTHRUG,
NEAR THE FENDER,(WITH ALICE’S LOVE).

Oh dear, what nonsense I’m talking!’
Just then her head struck against the roof of thehall: in fact she was now more than nine feet high,and she at once took up the little golden key andhurried off to the garden door.
Poor Alice! It was as much as she could do, lying
down on one side, to look through into the garden
with one eye; but to get through was more hopelessthan ever: she sat down and began to cry again.

(3)’I beg your pardon!’ said the Mouse, frowning, butvery politely: ’Did you speak?’’Not I!’ said the Lory hastily.
’I thought you did,’ said the Mouse. ’–I proceed. "Edwin and Morcar, the earls of Mercia
and Northumbria, declared for him: and even Stigand, the patriotic archbishop of Canterbury, foundit advisable–"’’Found WHAT?’ said the Duck.
’Found IT,’ the Mouse replied rather crossly: ’ofcourse you know what "it" means.’’I know what "it" means well enough, when I find athing,’ said the Duck: ’it’s generally a frog or a worm.
The question is, what did the archbishop find?’
The Mouse did not notice this question, but hurriedly went on, ’"–found it advisable to go with Edgar
Atheling to meet William and offer him the crown.
William’s conduct at first was moderate. But theinsolence of his Normans–" How are you getting onnow, my dear?’ it continued, turning to Alice as it
spoke.
’As wet as ever,’ said Alice in a melancholy tone:’it doesn’t seem to dry me at all.’’In that case,’ said the Dodo solemnly, rising to
its feet, ’I move that the meeting adjourn, for theimmediate adoption of more energetic remedies–’’Speak English!’ said the Eaglet. ’I don’t know themeaning of half those long words, and, what’s more,
I don’t believe you do either!’ And the Eaglet bent
down its head to hide a smile: some of the other birds
tittered audibly.
’What I was going to say,’ said the Dodo in an
offended tone, ’was, that the best thing to get us dry
would be a Caucus-race.’’What IS a Caucus-race?’ said Alice; not that she
wanted much to know, but the Dodo had paused as
if it thought that SOMEBODY ought to speak, andno one else seemed inclined to say anything.
’Why,’ said the Dodo, ’the best way to explain it
is to do it.’ (And, as you might like to try the thing
yourself, some winter day, I will tell you how the Dodo
managed it.)First it marked out a race-course, in a sort of circle,(’the exact shape doesn’t matter,’ it said,) and then
all the party were placed along the course, here andthere. There was no ’One, two, three, and away,’ butthey began running when they liked, and left off when
they liked, so that it was not easy to know when therace was over. However, when they had been runninghalf an hour or so, and were quite dry again, the Dodo
suddenly called out ’The race is over!’ and they all
crowded round it, panting, and asking, ’But who has
won?’This question the Dodo could not answer without agreat deal of thought, and it sat for a long time with
one finger pressed upon its forehead (the position inwhich you usually see Shakespeare, in the pictures ofhim), while the rest waited in silence. At last theDodo said, ’EVERYBODY has won, and all musthave prizes.’’But who is to give the prizes?’ quite a chorus ofvoices asked.
’Why, SHE, of course,’ said the Dodo, pointing to
Alice with one finger; and the whole party at once
crowded round her, calling out in a confused way,’Prizes! Prizes!’
Alice had no idea what to do, and in despair she
put her hand in her pocket, and pulled out a box ofcomfits, (luckily the salt water had not got into it),and handed them round as prizes. There was exactly
one a-piece all round.
’But she must have a prize herself, you know,’ said
the Mouse.
’Of course,’ the Dodo replied very gravely. ’Whatelse have you got in your pocket?’ he went on, turning
to Alice.
’Only a thimble,’ said Alice sadly.
’Hand it over here,’ said the Dodo.
Then they all crowded round her once more, while
the Dodo solemnly presented the thimble, saying’We beg your acceptance of this elegant thimble’;and, when it had finished this short speech, they all
cheered.
Alice thought the whole thing very absurd, butthey all looked so grave that she did not dare tolaugh; and, as she could not think of anything tosay, she simply bowed, and took the thimble, looking
as solemn as she could.
The next thing was to eat the comfits: this caused
some noise and confusion, as the large birds complained that they could not taste theirs, and the small
ones choked and had to be patted on the back. How-7
ever, it was over at last, and they sat down again ina ring, and begged the Mouse to tell them something
more.
’You promised to tell me your history, you know,’
said Alice, ’and why it is you hate–C and D,’ she
added in a whisper, half afraid that it would be offended again.
’Mine is a long and a sad tale!’ said the Mouse,turning to Alice, and sighing.
’It IS a long tail, certainly,’ said Alice, looking
down with wonder at the Mouse’s tail; ’but why do
you call it sad?’ And she kept on puzzling about it
while the Mouse was speaking, so that her idea of thetale was something like this:–(7)—
this sort of life! I do wonder what CAN have happened to me! When I used to read fairy-tales, I fancied that kind of thing never happened, and now here
I am in the middle of one! There ought to be a book
written about me, that there ought! And when I growup, I’ll write one–but I’m grown up now,’ she addedin a sorrowful tone; ’at least there’s no room to growup any more HERE.’’But then,’ thought Alice, ’shall I NEVER get any
older than I am now? That’ll be a comfort, one way–never to be an old woman–but then–always to havelessons to learn! Oh, I shouldn’t like THAT!’’Oh, you foolish Alice!’ she answered herself. ’How
can you learn lessons in here? Why, there’s hardly
room for YOU, and no room at all for any lessonbooks!’
And so she went on, taking first one side and thenthe other, and making quite a conversation of it altogether; but after a few minutes she heard a voiceoutside, and stopped to listen.
’Mary Ann! Mary Ann!’ said the voice. ’Fetch me
my gloves this moment!’ Then came a little patteringof feet on the stairs. Alice knew it was the Rabbit
coming to look for her, and she trembled till she shookthe house, quite forgetting that she was now about
a thousand times as large as the Rabbit, and had noreason to be afraid of it.
Presently the Rabbit came up to the door, andtried to open it; but, as the door opened inwards,
and Alice’s elbow was pressed hard against it, that
attempt proved a failure. Alice heard it say to itself’Then I’ll go round and get in at the window.’’THAT you won’t’ thought Alice, and, after waiting till she fancied she heard the Rabbit just under
the window, she suddenly spread out her hand, andmade a snatch in the air. She did not get hold of anything, but she heard a little shriek and a fall, and acrash of broken glass, from which she concluded that
it was just possible it had fallen into a cucumberframe, or something of the sort.
Next came an angry voice–the Rabbit’s–’Pat! Pat!
Where are you?’ And then a voice she had neverheard before, ’Sure then I’m here! Digging for apples,
yer honour!’3
same size: to be sure, this generally happens when
one eats cake, but Alice had got so much into theway of expecting nothing but out-of-the-way things
to happen, that it seemed quite dull and stupid forlife to go on in the common way.
So she set to work, and very soon finished off the
cake.

—

(6)

to cry again, for she felt very lonely and low-spirited. Alice! Come here directly, and get ready for yourIn a little while, however, she again heard a little walk!" "Coming in a minute, nurse! But I’ve got topattering of footsteps in the distance, and she looked see that the mouse doesn’t get out." Only I don’t
up eagerly, half hoping that the Mouse had changed think,’ Alice went on, ’that they’d let Dinah stop in
his mind, and was coming back to finish his story.
the house if it began ordering people about like that!’
By this time she had found her way into a tidy little room with a table in the window, and on it (asshe had hoped) a fan and two or three pairs of tiny
IV. The Rabbit Sends in awhite kid gloves: she took up the fan and a pair of the
gloves, and was just going to leave the room, when
Little Billher eye fell upon a little bottle that stood near theIt was the White Rabbit, trotting slowly back again, looking-glass. There was no label this time with theand looking anxiously about as it went, as if it had words ’DRINK ME,’ but nevertheless she uncorked it
lost something; and she heard it muttering to itself and put it to her lips. ’I know SOMETHING interest’The Duchess! The Duchess! Oh my dear paws! Oh ing is sure to happen,’ she said to herself, ’whenever I
my fur and whiskers! She’ll get me executed, as sure eat or drink anything; so I’ll just see what this bottle
as ferrets are ferrets! Where CAN I have dropped does. I do hope it’ll make me grow large again, forthem, I wonder?’ Alice guessed in a moment that really I’m quite tired of being such a tiny little thing!’
it was looking for the fan and the pair of white kid
It did so indeed, and much sooner than she had
gloves, and she very good-naturedly began hunting expected: before she had drunk half the bottle, sheabout for them, but they were nowhere to be seen– found her head pressing against the ceiling, and had
everything seemed to have changed since her swim in to stoop to save her neck from being broken. She
the pool, and the great hall, with the glass table and hastily put down the bottle, saying to herself ’That’s
the little door, had vanished completely.
quite enough–I hope I shan’t grow any more–As it is,
Very soon the Rabbit noticed Alice, as she went I can’t get out at the door–I do wish I hadn’t drunk
hunting about, and called out to her in an angry tone, quite so much!’’Why, Mary Ann, what ARE you doing out here?
Alas! it was too late to wish that! She went on
Run home this moment, and fetch me a pair of gloves growing, and growing, and very soon had to kneel
and a fan! Quick, now!’ And Alice was so much down on the floor: in another minute there was notfrightened that she ran off at once in the direction it even room for this, and she tried the effect of lying
pointed to, without trying to explain the mistake it down with one elbow against the door, and the otherhad made.
arm curled round her head. Still she went on growing,’He took me for his housemaid,’ she said to herself and, as a last resource, she put one arm out of theas she ran. ’How surprised he’ll be when he finds window, and one foot up the chimney, and said toout who I am! But I’d better take him his fan and herself ’Now I can do no more, whatever happens.
gloves–that is, if I can find them.’ As she said this, What WILL become of me?’she came upon a neat little house, on the door of
Luckily for Alice, the little magic bottle had now
which was a bright brass plate with the name ’W. had its full effect, and she grew no larger: still it was
RABBIT’ engraved upon it. She went in without very uncomfortable, and, as there seemed to be noknocking, and hurried upstairs, in great fear lest she sort of chance of her ever getting out of the roomshould meet the real Mary Ann, and be turned out again, no wonder she felt unhappy.
of the house before she had found the fan and gloves.
’It was much pleasanter at home,’ thought poor
’How queer it seems,’ Alice said to herself, ’to be Alice, ’when one wasn’t always growing larger andgoing messages for a rabbit! I suppose Dinah’ll be smaller, and being ordered about by mice and rabsending me on messages next!’ And she began fan- bits. I almost wish I hadn’t gone down that rabbitcying the sort of thing that would happen: ’"Miss hole–and yet–and yet–it’s rather curious, you know,

(9)

*
*

*

—
the shore, and then I’ll tell you my history, and you’ll
understand why it is I hate cats and dogs.’
It was high time to go, for the pool was getting
quite crowded with the birds and animals that had
fallen into it: there were a Duck and a Dodo, a Loryand an Eaglet, and several other curious creatures.
Alice led the way, and the whole party swam to theshore.

(5)’I had NOT!’ cried the Mouse, sharply and very
angrily.
’A knot!’ said Alice, always ready to make herself
useful, and looking anxiously about her. ’Oh, do letme help to undo it!’’I shall do nothing of the sort,’ said the Mouse, getting up and walking away. ’You insult me by talking
such nonsense!’’I didn’t mean it!’ pleaded poor Alice. ’But you’reso easily offended, you know!’
The Mouse only growled in reply.
’Please come back and finish your story!’ Alicecalled after it; and the others all joined in chorus,’Yes, please do!’ but the Mouse only shook its head
impatiently, and walked a little quicker.
’What a pity it wouldn’t stay!’ sighed the Lory, as
soon as it was quite out of sight; and an old Crab
took the opportunity of saying to her daughter ’Ah,
my dear! Let this be a lesson to you never to lose
YOUR temper!’ ’Hold your tongue, Ma!’ said the
young Crab, a little snappishly. ’You’re enough to
try the patience of an oyster!’’I wish I had our Dinah here, I know I do!’ said
Alice aloud, addressing nobody in particular. ’She’dsoon fetch it back!’’And who is Dinah, if I might venture to ask thequestion?’ said the Lory.
Alice replied eagerly, for she was always ready totalk about her pet: ’Dinah’s our cat. And she’s sucha capital one for catching mice you can’t think! And
oh, I wish you could see her after the birds! Why,
she’ll eat a little bird as soon as look at it!’This speech caused a remarkable sensation among
the party. Some of the birds hurried off at once: one
old Magpie began wrapping itself up very carefully,
remarking, ’I really must be getting home; the nightair doesn’t suit my throat!’ and a Canary called out
in a trembling voice to its children, ’Come away, mydears! It’s high time you were all in bed!’ On various
pretexts they all moved off, and Alice was soon left
alone.
’I wish I hadn’t mentioned Dinah!’ she said to’You are not attending!’ said the Mouse to Alice herself in a melancholy tone. ’Nobody seems to likeseverely. ’What are you thinking of?’her, down here, and I’m sure she’s the best cat in’I beg your pardon,’ said Alice very humbly: ’you the world! Oh, my dear Dinah! I wonder if I shallhad got to the fifth bend, I think?’
ever see you any more!’ And here poor Alice began(8)*’What a curious feeling!’ said Alice; ’I must be shutting up like a telescope.’

And so it was indeed: she was now only ten inches
high, and her face brightened up at the thought that
she was now the right size for going through the little door into that lovely garden. First, however, shewaited for a few minutes to see if she was going toshrink any further: she felt a little nervous about this;’for it might end, you know,’ said Alice to herself, ’in
my going out altogether, like a candle. I wonder what
I should be like then?’ And she tried to fancy what
the flame of a candle is like after the candle is blown
out, for she could not remember ever having seen sucha thing.
After a while, finding that nothing more happened,she decided on going into the garden at once; but, alasfor poor Alice! when she got to the door, she foundshe had forgotten the little golden key, and when she
went back to the table for it, she found she could
not possibly reach it: she could see it quite plainly
through the glass, and she tried her best to climb up
one of the legs of the table, but it was too slippery;
and when she had tired herself out with trying, thepoor little thing sat down and cried.
’Come, there’s no use in crying like that!’ said Alice to herself, rather sharply; ’I advise you to leave off
this minute!’ She generally gave herself very good advice, (though she very seldom followed it), and sometimes she scolded herself so severely as to bring tears
into her eyes; and once she remembered trying to box
her own ears for having cheated herself in a game ofcroquet she was playing against herself, for this curious child was very fond of pretending to be two
people. ’But it’s no use now,’ thought poor Alice,’to pretend to be two people! Why, there’s hardly
enough of me left to make ONE respectable person!’Soon her eye fell on a little glass box that was lying
under the table: she opened it, and found in it avery small cake, on which the words ’EAT ME’ werebeautifully marked in currants. ’Well, I’ll eat it,’ said
Alice, ’and if it makes me grow larger, I can reach
the key; and if it makes me grow smaller, I can creep
under the door; so either way I’ll get into the garden,
and I don’t care which happens!’
She ate a little bit, and said anxiously to herself,’Which way? Which way?’, holding her hand on the
top of her head to feel which way it was growing, andshe was quite surprised to find that she remained the

(2)
5

—
’Fury said to amouse, That hemet in thehouse,"Let usboth go tolaw: I willprosecuteYOU.--Come,
I’ll take nodenial; We
must have atrial: For
really thismorning I’ve
nothing
to do."
Said themouse to thecur, "Sucha trial,dear Sir,Withno juryor judge,
would bewastingourbreath.""I’ll bejudge, I’ll
be jury,"
Saidcunning
old Fury:"I’ll
try thewholecause,
andcondemnyoutodeath."’—
knelt down and looked along the passage into theloveliest garden you ever saw. How she longed toget out of that dark hall, and wander about among
those beds of bright flowers and those cool fountains,
but she could not even get her head through the doorway; ’and even if my head would go through,’ thoughtpoor Alice, ’it would be of very little use without myshoulders. Oh, how I wish I could shut up like a telescope! I think I could, if I only knew how to begin.’For, you see, so many out-of-the-way things had happened lately, that Alice had begun to think that very
few things indeed were really impossible.
There seemed to be no use in waiting by the little
door, so she went back to the table, half hoping she
might find another key on it, or at any rate a book ofrules for shutting people up like telescopes: this time
she found a little bottle on it, (’which certainly was
not here before,’ said Alice,) and round the neck of
the bottle was a paper label, with the words ’DRINKME’ beautifully printed on it in large letters.
It was all very well to say ’Drink me,’ but the wise
little Alice was not going to do THAT in a hurry.
’No, I’ll look first,’ she said, ’and see whether it’smarked "poison" or not’; for she had read several nicelittle histories about children who had got burnt, andeaten up by wild beasts and other unpleasant things,
all because they WOULD not remember the simple
rules their friends had taught them: such as, that a
red-hot poker will burn you if you hold it too long;and that if you cut your finger VERY deeply with aknife, it usually bleeds; and she had never forgotten
that, if you drink much from a bottle marked ’poison,’
it is almost certain to disagree with you, sooner orlater.
However, this bottle was NOT marked ’poison,’ so
Alice ventured to taste it, and finding it very nice,(it had, in fact, a sort of mixed flavour of cherrytart, custard, pine-apple, roast turkey, toffee, and hot
buttered toast,) she very soon finished it off.

—
’Digging for apples, indeed!’ said the Rabbit angrily. ’Here! Come and help me out of THIS!’(Sounds of more broken glass.)’Now tell me, Pat, what’s that in the window?’’Sure, it’s an arm, yer honour!’ (He pronounced it’arrum.’)’An arm, you goose! Who ever saw one that size?
Why, it fills the whole window!’’Sure, it does, yer honour: but it’s an arm for allthat.’’Well, it’s got no business there, at any rate: goand take it away!’
There was a long silence after this, and Alice could
only hear whispers now and then; such as, ’Sure, I
don’t like it, yer honour, at all, at all!’ ’Do as I
tell you, you coward!’ and at last she spread out her
hand again, and made another snatch in the air. This
time there were TWO little shrieks, and more soundsof broken glass. ’What a number of cucumber-frames
there must be!’ thought Alice. ’I wonder what they’ll
do next! As for pulling me out of the window, I only
wish they COULD! I’m sure I don’t want to stay inhere any longer!’
She waited for some time without hearing anything
more: at last came a rumbling of little cartwheels,and the sound of a good many voices all talking together: she made out the words: ’Where’s the otherladder?–Why, I hadn’t to bring but one; Bill’s got theother–Bill! fetch it here, lad!–Here, put ’em up at thiscorner–No, tie ’em together first–they don’t reachhalf high enough yet–Oh! they’ll do well enough;don’t be particular–Here, Bill! catch hold of thisrope–Will the roof bear?–Mind that loose slate–Oh,
it’s coming down! Heads below!’ (a loud crash)–’Now, who did that?–It was Bill, I fancy–Who’s to
go down the chimney?–Nay, I shan’t! YOU do it!–That I won’t, then!–Bill’s to go down–Here, Bill! themaster says you’re to go down the chimney!’’Oh! So Bill’s got to come down the chimney, hashe?’ said Alice to herself. ’Shy, they seem to put
everything upon Bill! I wouldn’t be in Bill’s place fora good deal: this fireplace is narrow, to be sure; but
I THINK I can kick a little!’
She drew her foot as far down the chimney as she
could, and waited till she heard a little animal (shecouldn’t guess of what sort it was) scratching and(10)

scrambling about in the chimney close above her:then, saying to herself ’This is Bill,’ she gave one
sharp kick, and waited to see what would happen
next.
The first thing she heard was a general chorus of’There goes Bill!’ then the Rabbit’s voice along–’Catch him, you by the hedge!’ then silence, andthen another confusion of voices–’Hold up his head–
Brandy now–Don’t choke him–How was it, old fellow?
What happened to you? Tell us all about it!’Last came a little feeble, squeaking voice, (’That’sBill,’ thought Alice,) ’Well, I hardly know–No more,thank ye; I’m better now–but I’m a deal too flustered
to tell you–all I know is, something comes at me likea Jack-in-the-box, and up I goes like a sky-rocket!’’So you did, old fellow!’ said the others.
’We must burn the house down!’ said the Rabbit’s
voice; and Alice called out as loud as she could, ’If
you do. I’ll set Dinah at you!’
There was a dead silence instantly, and Alicethought to herself, ’I wonder what they WILL do
next! If they had any sense, they’d take the roof
off.’ After a minute or two, they began moving about
again, and Alice heard the Rabbit say, ’A barrowful
will do, to begin with.’’A barrowful of WHAT?’ thought Alice; but she
had not long to doubt, for the next moment a showerof little pebbles came rattling in at the window, andsome of them hit her in the face. ’I’ll put a stopto this,’ she said to herself, and shouted out, ’You’dbetter not do that again!’ which produced anotherdead silence.
Alice noticed with some surprise that the pebbles
were all turning into little cakes as they lay on thefloor, and a bright idea came into her head. ’If I eat
one of these cakes,’ she thought, ’it’s sure to make
SOME change in my size; and as it can’t possibly
make me larger, it must make me smaller, I suppose.’
So she swallowed one of the cakes, and was delighted to find that she began shrinking directly. As
soon as she was small enough to get through the door,
she ran out of the house, and found quite a crowd oflittle animals and birds waiting outside. The poor little Lizard, Bill, was in the middle, being held up by
two guinea-pigs, who were giving it something out ofa bottle. They all made a rush at Alice the moment11
she appeared; but she ran off as hard as she could,
and soon found herself safe in a thick wood.
’The first thing I’ve got to do,’ said Alice to herself,
as she wandered about in the wood, ’is to grow to myright size again; and the second thing is to find myway into that lovely garden. I think that will be thebest plan.’
It sounded an excellent plan, no doubt, and very
neatly and simply arranged; the only difficulty was,that she had not the smallest idea how to set about
it; and while she was peering about anxiously among
the trees, a little sharp bark just over her head madeher look up in a great hurry.
An enormous puppy was looking down at her withlarge round eyes, and feebly stretching out one paw,
trying to touch her. ’Poor little thing!’ said Alice,in a coaxing tone, and she tried hard to whistle toit; but she was terribly frightened all the time at thethought that it might be hungry, in which case it
would be very likely to eat her up in spite of all her
coaxing.
Hardly knowing what she did, she picked up a little
bit of stick, and held it out to the puppy; whereupon
the puppy jumped into the air off all its feet at once,with a yelp of delight, and rushed at the stick, andmade believe to worry it; then Alice dodged behinda great thistle, to keep herself from being run over;and the moment she appeared on the other side, thepuppy made another rush at the stick, and tumbled
head over heels in its hurry to get hold of it; thenAlice, thinking it was very like having a game of playwith a cart-horse, and expecting every moment to be
trampled under its feet, ran round the thistle again;
then the puppy began a series of short charges at the
stick, running a very little way forwards each timeand a long way back, and barking hoarsely all thewhile, till at last it sat down a good way off, panting,with its tongue hanging out of its mouth, and its
great eyes half shut.
This seemed to Alice a good opportunity for making her escape; so she set off at once, and ran till she
was quite tired and out of breath, and till the puppy’s
bark sounded quite faint in the distance.
’And yet what a dear little puppy it was!’ said
Alice, as she leant against a buttercup to rest herself,
and fanned herself with one of the leaves: ’I should(11)

Defects: Too much white space in the second column on page 2, the first column on page 6 and again
in the first column of page 8 (the little bars above the columns give a visual indication of the column
badness from TEX’s perspective—longer means worse).
– A nearly empty column on page 7 because of the “mouse tail poem” is an unbreakable block.
– The first column on page 10 is one line too short because of a following 3-line paragraph that doesn’t
fit in its entirety (as widows/orphans are disallowed) and there is nothing in the column to stretch.
The grey-colored paragraphs (pages 2, 5 and 6) are those that are modified by the globally optimizing
algorithm to achieve the results shown in Figure 2 on the facing page.
F IGURE 1. Alice in Wonderland typeset with a greedy algorithm

In contrast, the algorithm presented in this paper is able to overcome all of these problems,
producing the results shown in Figure 2. It achieves this by manipulating the paragraphs
shown in grey in both figures and by running some of the page spreads short or long.
The example may seem to be spectacular, but the reality is that these kinds of defects
show up with nearly every document the moment it contains even only a small number of text
blocks that cannot be broken across columns, e.g., displayed formulas, headings that need
to be followed by a few lines of text, disallowed widows and orphans, etc., all of which arecommon cases in books or journal articles.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION—ALICE’S ADVENTURES IN WONDERLAND
Lewis Carroll
THE MILLENNIUM FULCRUM EDITION 3.0

12

out what she was coming to, but it was too dark to
see anything; then she looked at the sides of the well,and noticed that they were filled with cupboards andbook-shelves; here and there she saw maps and pictures hung upon pegs. She took down a jar fromone of the shelves as she passed; it was labelled ’ORANGE MARMALADE’, but to her great disappointment it was empty: she did not like to drop the jar
for fear of killing somebody, so managed to put it into
one of the cupboards as she fell past it.
’Well!’ thought Alice to herself, ’after such a fallas this, I shall think nothing of tumbling down stairs!
How brave they’ll all think me at home! Why, I
wouldn’t say anything about it, even if I fell off the
top of the house!’ (Which was very likely true.)
Down, down, down. Would the fall NEVER cometo an end! ’I wonder how many miles I’ve fallen by
this time?’ she said aloud. ’I must be getting somewhere near the centre of the earth. Let me see: thatwould be four thousand miles down, I think–’ (for,you see, Alice had learnt several things of this sort in
her lessons in the schoolroom, and though this was
not a VERY good opportunity for showing off her
knowledge, as there was no one to listen to her, still
it was good practice to say it over) ’–yes, that’s about
the right distance–but then I wonder what Latitude
or Longitude I’ve got to?’ (Alice had no idea what
Latitude was, or Longitude either, but thought they
were nice grand words to say.)Presently she began again. ’I wonder if I shall fallright THROUGH the earth! How funny it’ll seemto come out among the people that walk with theirheads downward! The Antipathies, I think–’ (she wasrather glad there WAS no one listening, this time, as
it didn’t sound at all the right word) ’–but I shallhave to ask them what the name of the country is,
you know. Please, Ma’am, is this New Zealand orAustralia?’ (and she tried to curtsey as she spoke–
fancy CURTSEYING as you’re falling through theair! Do you think you could manage it?) ’And what
an ignorant little girl she’ll think me for asking! No,
it’ll never do to ask: perhaps I shall see it written up
somewhere.’Down, down, down. There was nothing else to do,
so Alice soon began talking again. ’Dinah’ll miss mevery much to-night, I should think!’ (Dinah was the

I. Down the Rabbit-HoleAlice was beginning to get very tired of sitting by
her sister on the bank, and of having nothing to do:
once or twice she had peeped into the book her sister
was reading, but it had no pictures or conversationsin it, ’and what is the use of a book,’ thought Alice’without pictures or conversations?’
So she was considering in her own mind (as well as
she could, for the hot day made her feel very sleepy
and stupid), whether the pleasure of making a daisychain would be worth the trouble of getting up andpicking the daisies, when suddenly a White Rabbit
with pink eyes ran close by her.
There was nothing so VERY remarkable in that;nor did Alice think it so VERY much out of the way
to hear the Rabbit say to itself, ’Oh dear! Oh dear! I
shall be late!’ (when she thought it over afterwards,
it occurred to her that she ought to have wondered at
this, but at the time it all seemed quite natural); butwhen the Rabbit actually TOOK A WATCH OUT
OF ITS WAISTCOAT-POCKET, and looked at it,
and then hurried on, Alice started to her feet, for it
flashed across her mind that she had never before seen
a rabbit with either a waistcoat-pocket, or a watch
to take out of it, and burning with curiosity, she ran
across the field after it, and fortunately was just intime to see it pop down a large rabbit-hole under thehedge.
In another moment down went Alice after it, neveronce considering how in the world she was to get out
again.
The rabbit-hole went straight on like a tunnel forsome way, and then dipped suddenly down, so suddenly that Alice had not a moment to think about
stopping herself before she found herself falling downa very deep well.
Either the well was very deep, or she fell very
slowly, for she had plenty of time as she went down
to look about her and to wonder what was going tohappen next. First, she tried to look down and make—cat.) ’I hope they’ll remember her saucer of milk at
tea-time. Dinah my dear! I wish you were down herewith me! There are no mice in the air, I’m afraid, but
you might catch a bat, and that’s very like a mouse,
you know. But do cats eat bats, I wonder?’ And here
Alice began to get rather sleepy, and went on saying
to herself, in a dreamy sort of way, ’Do cats eat bats?
Do cats eat bats?’ and sometimes, ’Do bats eat cats?’
for, you see, as she couldn’t answer either question,
it didn’t much matter which way she put it. She feltthat she was dozing off, and had just begun to dreamthat she was walking hand in hand with Dinah, andsaying to her very earnestly, ’Now, Dinah, tell me
the truth: did you ever eat a bat?’ when suddenly,
thump! thump! down she came upon a heap of sticks
and dry leaves, and the fall was over.
Alice was not a bit hurt, and she jumped up on
to her feet in a moment: she looked up, but it was
all dark overhead; before her was another long passage, and the White Rabbit was still in sight, hurrying down it. There was not a moment to be lost:away went Alice like the wind, and was just in timeto hear it say, as it turned a corner, ’Oh my ears andwhiskers, how late it’s getting!’ She was close behind
it when she turned the corner, but the Rabbit was
no longer to be seen: she found herself in a long, lowhall, which was lit up by a row of lamps hanging fromthe roof.
There were doors all round the hall, but they were
all locked; and when Alice had been all the way down
one side and up the other, trying every door, shewalked sadly down the middle, wondering how she
was ever to get out again.
Suddenly she came upon a little three-legged table,
all made of solid glass; there was nothing on it except
a tiny golden key, and Alice’s first thought was thatit might belong to one of the doors of the hall; but,alas! either the locks were too large, or the key was
too small, but at any rate it would not open any ofthem. However, on the second time round, she cameupon a low curtain she had not noticed before, andbehind it was a little door about fifteen inches high:she tried the little golden key in the lock, and to her
great delight it fitted!
Alice opened the door and found that it led into asmall passage, not much larger than a rat-hole: she

(1)
4

—
go on crying in this way! Stop this moment, I tellyou!’ But she went on all the same, shedding gallons
of tears, until there was a large pool all round her,about four inches deep and reaching half down thehall.
After a time she heard a little pattering of feetin the distance, and she hastily dried her eyes to see
what was coming. It was the White Rabbit returning,splendidly dressed, with a pair of white kid gloves
in one hand and a large fan in the other: he cametrotting along in a great hurry, muttering to himself
as he came, ’Oh! the Duchess, the Duchess! Oh!
won’t she be savage if I’ve kept her waiting!’ Alice
felt so desperate that she was ready to ask help of any
one; so, when the Rabbit came near her, she began,in a low, timid voice, ’If you please, sir–’ The Rabbit
started violently, dropped the white kid gloves andthe fan, and skurried away into the darkness as hard
as he could go.
Alice took up the fan and gloves, and, as the hall
was very hot, she kept fanning herself all the time she
went on talking: ’Dear, dear! How queer everythingis to-day! And yesterday things went on just as usual.
I wonder if I’ve been changed in the night? Let me
think: was I the same when I got up this morning? I
almost think I can remember feeling a little different.
But if I’m not the same, the next question is, Who in
the world am I? Ah, THAT’S the great puzzle!’ And
she began thinking over all the children she knewthat were of the same age as herself, to see if she
could have been changed for any of them.
’I’m sure I’m not Ada,’ she said, ’for her hair goesin such long ringlets, and mine doesn’t go in ringlets
at all; and I’m sure I can’t be Mabel, for I know
all sorts of things, and she, oh! she knows such avery little! Besides, SHE’S she, and I’m I, and–ohdear, how puzzling it all is! I’ll try if I know all
the things I used to know. Let me see: four times
five is twelve, and four times six is thirteen, and fourtimes seven is–oh dear! I shall never get to twenty atthat rate! However, the Multiplication Table doesn’t
signify: let’s try Geography. London is the capital of
Paris, and Paris is the capital of Rome, and Rome–no, THAT’S all wrong, I’m certain! I must have beenchanged for Mabel! I’ll try and say "How doth thelittle–"’ and she crossed her hands on her lap as if shewere saying lessons, and began to repeat it, but her—
voice sounded hoarse and strange, and the words did
not come the same as they used to do:–’How doth the little crocodile
Improve his shining tail,And pour the waters of the Nile
On every golden scale!
’How cheerfully he seems to grin,
How neatly spread his claws,
And welcome little fishes inWith gently smiling jaws!’’I’m sure those are not the right words,’ said poor
Alice, and her eyes filled with tears again as she went
on, ’I must be Mabel after all, and I shall have to go
and live in that poky little house, and have next to
no toys to play with, and oh! ever so many lessons tolearn! No, I’ve made up my mind about it; if I’m Mabel, I’ll stay down here! It’ll be no use their putting
their heads down and saying "Come up again, dear!"
I shall only look up and say "Who am I then? Tellme that first, and then, if I like being that person, I’ll
come up: if not, I’ll stay down here till I’m somebody
else"–but, oh dear!’ cried Alice, with a sudden burstof tears, ’I do wish they WOULD put their heads
down! I am so VERY tired of being all alone here!’
As she said this she looked down at her hands, andwas surprised to see that she had put on one of the
Rabbit’s little white kid gloves while she was talking.
’How CAN I have done that?’ she thought. ’I must
be growing small again.’ She got up and went to
the table to measure herself by it, and found that, as
nearly as she could guess, she was now about two feethigh, and was going on shrinking rapidly: she soon
found out that the cause of this was the fan she washolding, and she dropped it hastily, just in time to
avoid shrinking away altogether.
’That WAS a narrow escape!’ said Alice, a gooddeal frightened at the sudden change, but very glad tofind herself still in existence; ’and now for the garden!’and she ran with all speed back to the little door:
but, alas! the little door was shut again, and the little
golden key was lying on the glass table as before, ’andthings are worse than ever,’ thought the poor child,’for I never was so small as this before, never! And I
declare it’s too bad, that it is!’As she said these words her foot slipped, and inanother moment, splash! she was up to her chin insalt water. Her first idea was that she had somehow fallen into the sea, ’and in that case I can goback by railway,’ she said to herself. (Alice had been
to the seaside once in her life, and had come to thegeneral conclusion, that wherever you go to on the
English coast you find a number of bathing machines
in the sea, some children digging in the sand withwooden spades, then a row of lodging houses, andbehind them a railway station.) However, she soon
made out that she was in the pool of tears which she
had wept when she was nine feet high.
’I wish I hadn’t cried so much!’ said Alice, as she
swam about, trying to find her way out. ’I shall bepunished for it now, I suppose, by being drowned in
my own tears! That WILL be a queer thing, to be
sure! However, everything is queer to-day.’Just then she heard something splashing about
in the pool a little way off, and she swam nearer
to make out what it was: at first she thought it
must be a walrus or hippopotamus, but then she
remembered how small she was now, and she soon
made out that it was only a mouse that had slippedin like herself.
’Would it be of any use, now,’ thought Alice, ’to
speak to this mouse? Everything is so out-of-theway down here, that I should think very likely it can
talk: at any rate, there’s no harm in trying.’ So shebegan: ’O Mouse, do you know the way out of thispool? I am very tired of swimming about here, O
Mouse!’ (Alice thought this must be the right wayof speaking to a mouse: she had never done such athing before, but she remembered having seen in her
brother’s Latin Grammar, ’A mouse–of a mouse–toa mouse–a mouse–O mouse!’) The Mouse looked ather rather inquisitively, and seemed to her to wink
with one of its little eyes, but it said nothing.
’Perhaps it doesn’t understand English,’ thought
Alice; ’I daresay it’s a French mouse, come over with
William the Conqueror.’ (For, with all her knowledgeof history, Alice had no very clear notion how long
ago anything had happened.) So she began again:’Ou est ma chatte?’ which was the first sentence inher French lesson-book. The Mouse gave a sudden
leap out of the water, and seemed to quiver all overwith fright. ’Oh, I beg your pardon!’ cried Alicehastily, afraid that she had hurt the poor animal’s
feelings. ’I quite forgot you didn’t like cats.’

(4)
8

(8)

6

’Not like cats!’ cried the Mouse, in a shrill, passionate voice. ’Would YOU like cats if you were me?’’Well, perhaps not,’ said Alice in a soothing tone:’don’t be angry about it. And yet I wish I could
show you our cat Dinah: I think you’d take a fancy
to cats if you could only see her. She is such a dear
quiet thing,’ Alice went on, half to herself, as she
swam lazily about in the pool, ’and she sits purringso nicely by the fire, licking her paws and washingher face–and she is such a nice soft thing to nurse–and she’s such a capital one for catching mice–oh, I
beg your pardon!’ cried Alice again, for this time theMouse was bristling all over, and she felt certain it
must be really offended. ’We won’t talk about her
any more if you’d rather not.’’We indeed!’ cried the Mouse, who was trembling
down to the end of his tail. ’As if I would talk onsuch a subject! Our family always HATED cats:
nasty, low, vulgar things! Don’t let me hear the nameagain!’’I won’t indeed!’ said Alice, in a great hurry tochange the subject of conversation. ’Are you–are you
fond–of–of dogs?’ The Mouse did not answer, so Alicewent on eagerly: ’There is such a nice little dog near
our house I should like to show you! A little brighteyed terrier, you know, with oh, such long curlybrown hair! And it’ll fetch things when you throw
them, and it’ll sit up and beg for its dinner, and allsorts of things–I can’t remember half of them–and it
belongs to a farmer, you know, and he says it’s so useful, it’s worth a hundred pounds! He says it kills all
the rats and–oh dear!’ cried Alice in a sorrowful tone,’I’m afraid I’ve offended it again!’ For the Mouse wasswimming away from her as hard as it could go, andmaking quite a commotion in the pool as it went.
So she called softly after it, ’Mouse dear! Do comeback again, and we won’t talk about cats or dogs
either, if you don’t like them!’ When the Mouse heard
this, it turned round and swam slowly back to her:its face was quite pale (with passion, Alice thought),
and it said in a low trembling voice, ’Let us get tothe shore, and then I’ll tell you my history, and you’ll
understand why it is I hate cats and dogs.’
It was high time to go, for the pool was getting
quite crowded with the birds and animals that had
fallen into it: there were a Duck and a Dodo, a Loryand an Eaglet, and several other curious creatures.

—
ever see you any more!’ And here poor Alice began
to cry again, for she felt very lonely and low-spirited.
In a little while, however, she again heard a little
pattering of footsteps in the distance, and she looked
up eagerly, half hoping that the Mouse had changed
his mind, and was coming back to finish his story.

IV. The Rabbit Sends in a
Little BillIt was the White Rabbit, trotting slowly back again,
and looking anxiously about as it went, as if it had
lost something; and she heard it muttering to itself’The Duchess! The Duchess! Oh my dear paws! Oh
my fur and whiskers! She’ll get me executed, as sure
as ferrets are ferrets! Where CAN I have dropped
them, I wonder?’ Alice guessed in a moment that
it was looking for the fan and the pair of white kid
gloves, and she very good-naturedly began hunting
about for them, but they were nowhere to be seen–
everything seemed to have changed since her swim in
the pool, and the great hall, with the glass table andthe little door, had vanished completely.
Very soon the Rabbit noticed Alice, as she went
hunting about, and called out to her in an angry tone,’Why, Mary Ann, what ARE you doing out here?
Run home this moment, and fetch me a pair of gloves
and a fan! Quick, now!’ And Alice was so muchfrightened that she ran off at once in the direction it
pointed to, without trying to explain the mistake it
had made.
’He took me for his housemaid,’ she said to herself
as she ran. ’How surprised he’ll be when he finds
out who I am! But I’d better take him his fan andgloves–that is, if I can find them.’ As she said this,she came upon a neat little house, on the door ofwhich was a bright brass plate with the name ’W.
RABBIT’ engraved upon it. She went in without
knocking, and hurried upstairs, in great fear lest sheshould meet the real Mary Ann, and be turned outof the house before she had found the fan and gloves.
’How queer it seems,’ Alice said to herself, ’to be
going messages for a rabbit! I suppose Dinah’ll besending me on messages next!’ And she began fancying the sort of thing that would happen: ’"MissAlice! Come here directly, and get ready for yourwalk!" "Coming in a minute, nurse! But I’ve got to
see that the mouse doesn’t get out." Only I don’t
think,’ Alice went on, ’that they’d let Dinah stop in
the house if it began ordering people about like that!’
By this time she had found her way into a tidy little room with a table in the window, and on it (asshe had hoped) a fan and two or three pairs of tiny
white kid gloves: she took up the fan and a pair of the
gloves, and was just going to leave the room, whenher eye fell upon a little bottle that stood near thelooking-glass. There was no label this time with thewords ’DRINK ME,’ but nevertheless she uncorked it
and put it to her lips. ’I know SOMETHING interesting is sure to happen,’ she said to herself, ’whenever I
eat or drink anything; so I’ll just see what this bottle
does. I do hope it’ll make me grow large again, forreally I’m quite tired of being such a tiny little thing!’
It did so indeed, and much sooner than she had
expected: before she had drunk half the bottle, shefound her head pressing against the ceiling, and had
to stoop to save her neck from being broken. She
hastily put down the bottle, saying to herself ’That’squite enough–I hope I shan’t grow any more–As it is,I can’t get out at the door–I do wish I hadn’t drunkquite so much!’
Alas! it was too late to wish that! She went on
growing, and growing, and very soon had to kneel
down on the floor: in another minute there was noteven room for this, and she tried the effect of lying
down with one elbow against the door, and the otherarm curled round her head. Still she went on growing,
and, as a last resource, she put one arm out of thewindow, and one foot up the chimney, and said toherself ’Now I can do no more, whatever happens.
What WILL become of me?’Luckily for Alice, the little magic bottle had now
had its full effect, and she grew no larger: still it wasvery uncomfortable, and, as there seemed to be nosort of chance of her ever getting out of the room
again, no wonder she felt unhappy.
’It was much pleasanter at home,’ thought poor
Alice, ’when one wasn’t always growing larger and

*

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*

’What a curious feeling!’ said Alice; ’I must be shutting up like a telescope.’
And so it was indeed: she was now only ten inches
high, and her face brightened up at the thought that

she was now the right size for going through the little door into that lovely garden. First, however, shewaited for a few minutes to see if she was going toshrink any further: she felt a little nervous about this;’for it might end, you know,’ said Alice to herself, ’in
my going out altogether, like a candle. I wonder what
I should be like then?’ And she tried to fancy what
the flame of a candle is like after the candle is blown
out, for she could not remember ever having seen sucha thing.
After a while, finding that nothing more happened,she decided on going into the garden at once; but, alasfor poor Alice! when she got to the door, she foundshe had forgotten the little golden key, and when she
went back to the table for it, she found she could
not possibly reach it: she could see it quite plainly
through the glass, and she tried her best to climb up
one of the legs of the table, but it was too slippery;
and when she had tired herself out with trying, thepoor little thing sat down and cried.
’Come, there’s no use in crying like that!’ said Alice to herself, rather sharply; ’I advise you to leave off
this minute!’ She generally gave herself very good advice, (though she very seldom followed it), and sometimes she scolded herself so severely as to bring tears
into her eyes; and once she remembered trying to box
her own ears for having cheated herself in a game ofcroquet she was playing against herself, for this curious child was very fond of pretending to be two
people. ’But it’s no use now,’ thought poor Alice,’to pretend to be two people! Why, there’s hardly
enough of me left to make ONE respectable person!’Soon her eye fell on a little glass box that was lying
under the table: she opened it, and found in it avery small cake, on which the words ’EAT ME’ werebeautifully marked in currants. ’Well, I’ll eat it,’ said
Alice, ’and if it makes me grow larger, I can reach
the key; and if it makes me grow smaller, I can creep
under the door; so either way I’ll get into the garden,
and I don’t care which happens!’
She ate a little bit, and said anxiously to herself,’Which way? Which way?’, holding her hand on the
top of her head to feel which way it was growing, andshe was quite surprised to find that she remained thesame size: to be sure, this generally happens when
one eats cake, but Alice had got so much into the

Alice led the way, and the whole party swam to theshore.

III. A Caucus-Race and aLong Tale
They were indeed a queer-looking party that assembled on the bank–the birds with draggled feathers,
the animals with their fur clinging close to them, andall dripping wet, cross, and uncomfortable.
The first question of course was, how to get dry
again: they had a consultation about this, and aftera few minutes it seemed quite natural to Alice tofind herself talking familiarly with them, as if she had
known them all her life. Indeed, she had quite a longargument with the Lory, who at last turned sulky,
and would only say, ’I am older than you, and must
know better’; and this Alice would not allow without
knowing how old it was, and, as the Lory positively
refused to tell its age, there was no more to be said.
At last the Mouse, who seemed to be a personof authority among them, called out, ’Sit down, allof you, and listen to me! I’LL soon make you dry
enough!’ They all sat down at once, in a large ring,with the Mouse in the middle. Alice kept her eyes
anxiously fixed on it, for she felt sure she would catcha bad cold if she did not get dry very soon.
’Ahem!’ said the Mouse with an important air,’are you all ready? This is the driest thing I know.
Silence all round, if you please! "William the Conqueror, whose cause was favoured by the pope, wassoon submitted to by the English, who wanted leaders, and had been of late much accustomed to usurpation and conquest. Edwin and Morcar, the earls ofMercia and Northumbria–"’’Ugh!’ said the Lory, with a shiver.
’I beg your pardon!’ said the Mouse, frowning, butvery politely: ’Did you speak?’’Not I!’ said the Lory hastily.
’I thought you did,’ said the Mouse. ’–I proceed. "Edwin and Morcar, the earls of Mercia
and Northumbria, declared for him: and even Stigand, the patriotic archbishop of Canterbury, foundit advisable–"’’Found WHAT?’ said the Duck.

9

10

*

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*
*

*

*

II. The Pool of Tears’Curiouser and curiouser!’ cried Alice (she was somuch surprised, that for the moment she quite forgot
how to speak good English); ’now I’m opening out
like the largest telescope that ever was! Good-bye,feet!’ (for when she looked down at her feet, they
seemed to be almost out of sight, they were getting
so far off). ’Oh, my poor little feet, I wonder who will
put on your shoes and stockings for you now, dears?
I’m sure I shan’t be able! I shall be a great deal too
far off to trouble myself about you: you must manage
the best way you can;–but I must be kind to them,’
thought Alice, ’or perhaps they won’t walk the way I
want to go! Let me see: I’ll give them a new pair ofboots every Christmas.’
And she went on planning to herself how she
would manage it. ’They must go by the carrier,’ shethought; ’and how funny it’ll seem, sending presents
to one’s own feet! And how odd the directions will
look!
ALICE’S RIGHT FOOT, ESQ.
HEARTHRUG,
NEAR THE FENDER,(WITH ALICE’S LOVE).

Oh dear, what nonsense I’m talking!’
Just then her head struck against the roof of thehall: in fact she was now more than nine feet high,and she at once took up the little golden key andhurried off to the garden door.
Poor Alice! It was as much as she could do, lying
down on one side, to look through into the garden
with one eye; but to get through was more hopelessthan ever: she sat down and began to cry again.
’You ought to be ashamed of yourself,’ said Alice,’a great girl like you,’ (she might well say this), ’to—’Found IT,’ the Mouse replied rather crossly: ’ofcourse you know what "it" means.’’I know what "it" means well enough, when I find athing,’ said the Duck: ’it’s generally a frog or a worm.
The question is, what did the archbishop find?’
The Mouse did not notice this question, but hurriedly went on, ’"–found it advisable to go with Edgar
Atheling to meet William and offer him the crown.
William’s conduct at first was moderate. But the insolence of his Normans–" How are you getting on now,
my dear?’ it continued, turning to Alice as it spoke.
’As wet as ever,’ said Alice in a melancholy tone:’it doesn’t seem to dry me at all.’’In that case,’ said the Dodo solemnly, rising to
its feet, ’I move that the meeting adjourn, for theimmediate adoption of more energetic remedies–’’Speak English!’ said the Eaglet. ’I don’t know themeaning of half those long words, and, what’s more,
I don’t believe you do either!’ And the Eaglet bent
down its head to hide a smile: some of the other birds
tittered audibly.
’What I was going to say,’ said the Dodo in an
offended tone, ’was, that the best thing to get us dry
would be a Caucus-race.’’What IS a Caucus-race?’ said Alice; not that she
wanted much to know, but the Dodo had paused as
if it thought that SOMEBODY ought to speak, andno one else seemed inclined to say anything.
’Why,’ said the Dodo, ’the best way to explain it
is to do it.’ (And, as you might like to try the thing
yourself, some winter day, I will tell you how the Dodo
managed it.)First it marked out a race-course, in a sort of circle,(’the exact shape doesn’t matter,’ it said,) and then
all the party were placed along the course, here andthere. There was no ’One, two, three, and away,’ butthey began running when they liked, and left off when
they liked, so that it was not easy to know when therace was over. However, when they had been runninghalf an hour or so, and were quite dry again, the Dodo
suddenly called out ’The race is over!’ and they all
crowded round it, panting, and asking, ’But who has
won?’This question the Dodo could not answer without agreat deal of thought, and it sat for a long time with
one finger pressed upon its forehead (the position inwhich you usually see Shakespeare, in the pictures ofhim), while the rest waited in silence. At last theDodo said, ’EVERYBODY has won, and all musthave prizes.’’But who is to give the prizes?’ quite a chorus ofvoices asked.
’Why, SHE, of course,’ said the Dodo, pointing to
Alice with one finger; and the whole party at once
crowded round her, calling out in a confused way,’Prizes! Prizes!’
Alice had no idea what to do, and in despair she
put her hand in her pocket, and pulled out a box ofcomfits, (luckily the salt water had not got into it),and handed them round as prizes. There was exactly
one a-piece all round.
’But she must have a prize herself, you know,’ said
the Mouse.
’Of course,’ the Dodo replied very gravely. ’Whatelse have you got in your pocket?’ he went on, turning
to Alice.
’Only a thimble,’ said Alice sadly.
’Hand it over here,’ said the Dodo.
Then they all crowded round her once more, while
the Dodo solemnly presented the thimble, saying’We beg your acceptance of this elegant thimble’;and, when it had finished this short speech, they all
cheered.
Alice thought the whole thing very absurd, butthey all looked so grave that she did not dare tolaugh; and, as she could not think of anything tosay, she simply bowed, and took the thimble, looking
as solemn as she could.
The next thing was to eat the comfits: this caused
some noise and confusion, as the large birds complained that they could not taste theirs, and the small
ones choked and had to be patted on the back. However, it was over at last, and they sat down again ina ring, and begged the Mouse to tell them something
more.
’You promised to tell me your history, you know,’
said Alice, ’and why it is you hate–C and D,’ she
added in a whisper, half afraid that it would be offended again.
’Mine is a long and a sad tale!’ said the Mouse,turning to Alice, and sighing.
’It IS a long tail, certainly,’ said Alice, looking
down with wonder at the Mouse’s tail; ’but why do
you call it sad?’ And she kept on puzzling about it

7
while the Mouse was speaking, so that her idea of thetale was something like this:–’Fury said to amouse, That hemet in thehouse,"Let usboth go tolaw: I willprosecuteYOU.--Come,
I’ll take nodenial; We
must have atrial: For
really thismorning I’ve
nothing
to do."
Said themouse to thecur, "Sucha trial,dear Sir,Withno juryor judge,
would bewastingourbreath.""I’ll bejudge, I’ll
be jury,"
Saidcunning
old Fury:"I’ll
try thewholecause,
andcondemnyoutodeath."’’You are not attending!’ said the Mouse to Aliceseverely. ’What are you thinking of?’’I beg your pardon,’ said Alice very humbly: ’you
had got to the fifth bend, I think?’(7)—
heard before, ’Sure then I’m here! Digging for apples,
yer honour!’’Digging for apples, indeed!’ said the Rabbit angrily. ’Here! Come and help me out of THIS!’(Sounds of more broken glass.)’Now tell me, Pat, what’s that in the window?’’Sure, it’s an arm, yer honour!’ (He pronounced it’arrum.’)’An arm, you goose! Who ever saw one that size?
Why, it fills the whole window!’’Sure, it does, yer honour: but it’s an arm for allthat.’’Well, it’s got no business there, at any rate: goand take it away!’
There was a long silence after this, and Alice could
only hear whispers now and then; such as, ’Sure, I
don’t like it, yer honour, at all, at all!’ ’Do as I
tell you, you coward!’ and at last she spread out her
hand again, and made another snatch in the air. This
time there were TWO little shrieks, and more soundsof broken glass. ’What a number of cucumber-frames
there must be!’ thought Alice. ’I wonder what they’ll
do next! As for pulling me out of the window, I only
wish they COULD! I’m sure I don’t want to stay inhere any longer!’
She waited for some time without hearing anything
more: at last came a rumbling of little cartwheels,and the sound of a good many voices all talking together: she made out the words: ’Where’s the otherladder?–Why, I hadn’t to bring but one; Bill’s got theother–Bill! fetch it here, lad!–Here, put ’em up at thiscorner–No, tie ’em together first–they don’t reachhalf high enough yet–Oh! they’ll do well enough;don’t be particular–Here, Bill! catch hold of thisrope–Will the roof bear?–Mind that loose slate–Oh,
it’s coming down! Heads below!’ (a loud crash)–’Now, who did that?–It was Bill, I fancy–Who’s to
go down the chimney?–Nay, I shan’t! YOU do it!–That I won’t, then!–Bill’s to go down–Here, Bill! themaster says you’re to go down the chimney!’’Oh! So Bill’s got to come down the chimney, hashe?’ said Alice to herself. ’Shy, they seem to put
everything upon Bill! I wouldn’t be in Bill’s place fora good deal: this fireplace is narrow, to be sure; but
I THINK I can kick a little!’

3
way of expecting nothing but out-of-the-way things
to happen, that it seemed quite dull and stupid forlife to go on in the common way.
So she set to work, and very soon finished off the
cake.

(3)

—

(6)

smaller, and being ordered about by mice and rabbits. I almost wish I hadn’t gone down that rabbithole–and yet–and yet–it’s rather curious, you know,
this sort of life! I do wonder what CAN have happened to me! When I used to read fairy-tales, I fancied that kind of thing never happened, and now here
I am in the middle of one! There ought to be a book
written about me, that there ought! And when I growup, I’ll write one–but I’m grown up now,’ she addedin a sorrowful tone; ’at least there’s no room to growup any more HERE.’’But then,’ thought Alice, ’shall I NEVER get any
older than I am now? That’ll be a comfort, one way–never to be an old woman–but then–always to havelessons to learn! Oh, I shouldn’t like THAT!’’Oh, you foolish Alice!’ she answered herself. ’How
can you learn lessons in here? Why, there’s hardly
room for YOU, and no room at all for any lessonbooks!’
And so she went on, taking first one side and thenthe other, and making quite a conversation of it altogether; but after a few minutes she heard a voiceoutside, and stopped to listen.
’Mary Ann! Mary Ann!’ said the voice. ’Fetch me
my gloves this moment!’ Then came a little patteringof feet on the stairs. Alice knew it was the Rabbit
coming to look for her, and she trembled till she shookthe house, quite forgetting that she was now about
a thousand times as large as the Rabbit, and had noreason to be afraid of it.
Presently the Rabbit came up to the door, andtried to open it; but, as the door opened inwards,
and Alice’s elbow was pressed hard against it, that
attempt proved a failure. Alice heard it say to itself’Then I’ll go round and get in at the window.’’THAT you won’t’ thought Alice, and, after waiting till she fancied she heard the Rabbit just under
the window, she suddenly spread out her hand, andmade a snatch in the air. She did not get hold of anything, but she heard a little shriek and a fall, and acrash of broken glass, from which she concluded that
it was just possible it had fallen into a cucumberframe, or something of the sort.
Next came an angry voice–the Rabbit’s–’Pat! Pat!
Where are you?’ And then a voice she had never(9)—
knelt down and looked along the passage into theloveliest garden you ever saw. How she longed toget out of that dark hall, and wander about among
those beds of bright flowers and those cool fountains,
but she could not even get her head through the doorway; ’and even if my head would go through,’ thoughtpoor Alice, ’it would be of very little use without myshoulders. Oh, how I wish I could shut up like a telescope! I think I could, if I only knew how to begin.’For, you see, so many out-of-the-way things had happened lately, that Alice had begun to think that very
few things indeed were really impossible.
There seemed to be no use in waiting by the little
door, so she went back to the table, half hoping she
might find another key on it, or at any rate a book ofrules for shutting people up like telescopes: this time
she found a little bottle on it, (’which certainly was
not here before,’ said Alice,) and round the neck of
the bottle was a paper label, with the words ’DRINKME’ beautifully printed on it in large letters.
It was all very well to say ’Drink me,’ but the wise
little Alice was not going to do THAT in a hurry. ’No,
I’ll look first,’ she said, ’and see whether it’s marked"poison" or not’; for she had read several nice little
histories about children who had got burnt, and eaten
up by wild beasts and other unpleasant things, allbecause they WOULD not remember the simple rules
their friends had taught them: such as, that a red-hot
poker will burn you if you hold it too long; and that
if you cut your finger VERY deeply with a knife, it
usually bleeds; and she had never forgotten that, if
you drink much from a bottle marked ’poison,’ it isalmost certain to disagree with you, sooner or later.
However, this bottle was NOT marked ’poison,’ so
Alice ventured to taste it, and finding it very nice,(it had, in fact, a sort of mixed flavour of cherrytart, custard, pine-apple, roast turkey, toffee, and hot
buttered toast,) she very soon finished it off.

(2)
5

(5)

—
’I had NOT!’ cried the Mouse, sharply and very
angrily.
’A knot!’ said Alice, always ready to make herself
useful, and looking anxiously about her. ’Oh, do letme help to undo it!’’I shall do nothing of the sort,’ said the Mouse, getting up and walking away. ’You insult me by talking
such nonsense!’’I didn’t mean it!’ pleaded poor Alice. ’But you’reso easily offended, you know!’
The Mouse only growled in reply.
’Please come back and finish your story!’ Alicecalled after it; and the others all joined in chorus,’Yes, please do!’ but the Mouse only shook its head
impatiently, and walked a little quicker.
’What a pity it wouldn’t stay!’ sighed the Lory, as
soon as it was quite out of sight; and an old Crab
took the opportunity of saying to her daughter ’Ah,
my dear! Let this be a lesson to you never to lose
YOUR temper!’ ’Hold your tongue, Ma!’ said the
young Crab, a little snappishly. ’You’re enough to
try the patience of an oyster!’’I wish I had our Dinah here, I know I do!’ said
Alice aloud, addressing nobody in particular. ’She’dsoon fetch it back!’’And who is Dinah, if I might venture to ask thequestion?’ said the Lory.
Alice replied eagerly, for she was always ready totalk about her pet: ’Dinah’s our cat. And she’s sucha capital one for catching mice you can’t think! And
oh, I wish you could see her after the birds! Why,
she’ll eat a little bird as soon as look at it!’This speech caused a remarkable sensation among
the party. Some of the birds hurried off at once: one
old Magpie began wrapping itself up very carefully,
remarking, ’I really must be getting home; the nightair doesn’t suit my throat!’ and a Canary called out
in a trembling voice to its children, ’Come away, mydears! It’s high time you were all in bed!’ On various
pretexts they all moved off, and Alice was soon left
alone.
’I wish I hadn’t mentioned Dinah!’ she said toherself in a melancholy tone. ’Nobody seems to likeher, down here, and I’m sure she’s the best cat in
the world! Oh, my dear Dinah! I wonder if I shall5—
She drew her foot as far down the chimney as she
could, and waited till she heard a little animal (shecouldn’t guess of what sort it was) scratching andscrambling about in the chimney close above her:then, saying to herself ’This is Bill,’ she gave one
sharp kick, and waited to see what would happen
next.
The first thing she heard was a general chorus of’There goes Bill!’ then the Rabbit’s voice along–’Catch him, you by the hedge!’ then silence, andthen another confusion of voices–’Hold up his head–
Brandy now–Don’t choke him–How was it, old fellow?
What happened to you? Tell us all about it!’Last came a little feeble, squeaking voice, (’That’sBill,’ thought Alice,) ’Well, I hardly know–No more,thank ye; I’m better now–but I’m a deal too flustered
to tell you–all I know is, something comes at me likea Jack-in-the-box, and up I goes like a sky-rocket!’’So you did, old fellow!’ said the others.
’We must burn the house down!’ said the Rabbit’s
voice; and Alice called out as loud as she could, ’If
you do. I’ll set Dinah at you!’
There was a dead silence instantly, and Alicethought to herself, ’I wonder what they WILL do
next! If they had any sense, they’d take the roof
off.’ After a minute or two, they began moving about
again, and Alice heard the Rabbit say, ’A barrowful
will do, to begin with.’’A barrowful of WHAT?’ thought Alice; but she
had not long to doubt, for the next moment a showerof little pebbles came rattling in at the window, andsome of them hit her in the face. ’I’ll put a stopto this,’ she said to herself, and shouted out, ’You’dbetter not do that again!’ which produced anotherdead silence.
Alice noticed with some surprise that the pebbles
were all turning into little cakes as they lay on thefloor, and a bright idea came into her head. ’If I eat
one of these cakes,’ she thought, ’it’s sure to make
SOME change in my size; and as it can’t possibly
make me larger, it must make me smaller, I suppose.’
So she swallowed one of the cakes, and was delighted to find that she began shrinking directly. As
soon as she was small enough to get through the door,
she ran out of the house, and found quite a crowd of(10)

little animals and birds waiting outside. The poor little Lizard, Bill, was in the middle, being held up by
two guinea-pigs, who were giving it something out ofa bottle. They all made a rush at Alice the moment
she appeared; but she ran off as hard as she could,
and soon found herself safe in a thick wood.
’The first thing I’ve got to do,’ said Alice to herself,
as she wandered about in the wood, ’is to grow to myright size again; and the second thing is to find myway into that lovely garden. I think that will be thebest plan.’
It sounded an excellent plan, no doubt, and very
neatly and simply arranged; the only difficulty was,that she had not the smallest idea how to set about
it; and while she was peering about anxiously among
the trees, a little sharp bark just over her head madeher look up in a great hurry.
An enormous puppy was looking down at her withlarge round eyes, and feebly stretching out one paw,
trying to touch her. ’Poor little thing!’ said Alice,in a coaxing tone, and she tried hard to whistle toit; but she was terribly frightened all the time at thethought that it might be hungry, in which case it
would be very likely to eat her up in spite of all her
coaxing.
Hardly knowing what she did, she picked up a little
bit of stick, and held it out to the puppy; whereupon
the puppy jumped into the air off all its feet at once,with a yelp of delight, and rushed at the stick, andmade believe to worry it; then Alice dodged behinda great thistle, to keep herself from being run over;and the moment she appeared on the other side, thepuppy made another rush at the stick, and tumbled
head over heels in its hurry to get hold of it; thenAlice, thinking it was very like having a game of playwith a cart-horse, and expecting every moment to be
trampled under its feet, ran round the thistle again;
then the puppy began a series of short charges at the
stick, running a very little way forwards each timeand a long way back, and barking hoarsely all thewhile, till at last it sat down a good way off, panting,with its tongue hanging out of its mouth, and its
great eyes half shut.
This seemed to Alice a good opportunity for making her escape; so she set off at once, and ran till she

11
was quite tired and out of breath, and till the puppy’s
bark sounded quite faint in the distance.
’And yet what a dear little puppy it was!’ said
Alice, as she leant against a buttercup to rest herself,
and fanned herself with one of the leaves: ’I shouldhave liked teaching it tricks very much, if–if I’d only
been the right size to do it! Oh dear! I’d nearly
forgotten that I’ve got to grow up again! Let me see–
how IS it to be managed? I suppose I ought to eat
or drink something or other; but the great questionis, what?’
The great question certainly was, what? Alicelooked all round her at the flowers and the bladesof grass, but she did not see anything that looked
like the right thing to eat or drink under the circumstances. There was a large mushroom growing nearher, about the same height as herself; and when she
had looked under it, and on both sides of it, and behind it, it occurred to her that she might as well lookand see what was on the top of it.
She stretched herself up on tiptoe, and peeped overthe edge of the mushroom, and her eyes immediately
met those of a large caterpillar, that was sitting on
the top with its arms folded, quietly smoking a long
hookah, and taking not the smallest notice of her orof anything else.

V. Advice from a Caterpillar
The Caterpillar and Alice looked at each other forsome time in silence: at last the Caterpillar took thehookah out of its mouth, and addressed her in a languid, sleepy voice.
’Who are YOU?’ said the Caterpillar.
This was not an encouraging opening for a conversation. Alice replied, rather shyly, ’I–I hardly know,
sir, just at present–at least I know who I WAS when
I got up this morning, but I think I must have beenchanged several times since then.’’What do you mean by that?’ said the Caterpillar
sternly. ’Explain yourself!’’I can’t explain MYSELF, I’m afraid, sir’ said Alice, ’because I’m not myself, you see.’’I don’t see,’ said the Caterpillar.

(11)

Corrective actions compared to the greedy algorithm:– Shortened a paragraph in second column of page 2. Lengthened pages 4–7 by one line.
– On page 5 lengthened one paragraph in first column and shortened one in second column. Net effectis zero but it avoids an orphan at the end of the first column.
– Shortened two paragraphs on page 6 to allow the “mouse tail poem” to move back to page 7.
– Shortened pages 8–11 by one line to avoid some orphans and widows.
The grey colored paragraphs (pages 2, 5 and 6) are those that have been lengthened or shortened by the
globally optimizing algorithm. Compare with the results from the greedy algorithm shown in Figure 1.

F IGURE 2. Alice in Wonderland typeset with an optimizing algorithm
1.3. Global optimization
When we speak of “globally optimized pagination” we mean that out of all possible
paginations for a given document the “best” by some measure is selected. To determine thisoptimal pagination we define a function that, when given a pagination as input, will return asingle numerical value. By convention a lower value indicates a better result, hence common
names for such functions in literature are “cost function” or “objective function” as one
can view this as returning the costs associated with its input. Finding the optimal solution
therefore means finding the pagination that results in the lowest return value of this function.

6

C OMPUTATIONAL I NTELLIGENCE

Taking a step back from that rather abstract definition of a quality measure, what does itmean in reality and how can it be applied? Obviously, if we can measure a specific aspect of apagination, we can attach a value to it and this can be done in a such way that lower values
correspond to better results for this particular aspect.
For example, if we are interested in a low number of pages we could return #pages or(#pages)2 . Or, if we want to measure the quality of the white space distribution for a given
pagination, we could analyze the quality of each column (obtaining a number greater thanzero, if there is excess white space) and then sum these up over all columns, or sum up thesquares of these values or use the maximum over all columns or . . .
All these examples are valid measures in the sense that they encode the quality of a certain
aspect in a monotone function, but clearly they are quite different and focus on different
sub-aspects. For example, if we take the sum then this means that a single very bad column
among a lot of perfect ones is considered to be better than a few near-perfect columns whereas
summing the squares will give a better result if all values are closer to each other. Thus, evenfor a single quality aspect it can turn out to be a difficult problem to define a cost function thatis a reasonable approximation to the quality perception of a human looking at the paginations.
But to make matters worse, we need to deal not with one but with several different quality
aspects but still come up in real life with a single number that encompasses them all. This canthen be used to determine the overall optimal solution, which is commonly done by adding
up the values for each aspect after weighting each of them by a factor (a weighted sum). Very
many other methods and adjustments are available for combining these values to give a single
number. Each gives a new twist on the algorithm’s understanding of “quality”.
Summing up, an optimal solution is only optimal with respect to the quality measurethat is encoded in the objective function used to determine it. If that function is defective sowill be the algorithm’s result. Furthermore, correctly weighting different aspects against eachother (even if only a small number of aspects are part of the equation) is a difficult art andrequires some experimentation to achieve acceptable results.3
There is thus a need for a flexible framework, one that allows the user of such an algorithm
to specify their vision of quality in the form of constraints and relationships between different
goals; and also enables them to approximate this vision as closely as possible in the objectivefunction used during optimization. Section 1.6 gives a preliminary overview on the constraints
and flexibility available in the framework described in this paper. Later sections then zoom in
on individual constraints, their implementations and discuss the relationships between them.
1.4. Pagination strategies and related work
While Knuth and Plass (1981) already introduced global optimization for micro-typography in TEX in the ’80s, pagination in today’s systems is still undertaken using greedy
algorithms that essentially generate column by column without looking (far) ahead.
Already in his PhD thesis Plass (1981) discussed applying the ideas behind TEX’s linebreaking algorithm to the question of paginating documents containing text and floats. Since
then a number of other researchers have worked on improved pagination algorithms, e.g.,
Wohlfeil (1998) addressed optimal float placement for certain types of documents in his PhD
thesis and together with Brüggemann-Klein et al. (2003) using dynamic programming basedon the Knuth/Plass algorithm with a restricted document model. Jacobs et al. (2003) explore
the use of layout templates that can be selected by an optimizing algorithm also based on
Knuth/Plass to best fulfill a number of constraints.
3 During the development the author was several times quite surprised by the changes in the solution chosen by the framework

when making minor changes to some constraints. In a few cases this revealed a hidden bug in the implementation, but usually it
was due to the algorithm sacrificing the quality of one aspect in one part to get a better result for some other aspect elsewhere.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

7

Ciancarini et al. (2012) present an approach (again based on Knuth/Plass) in which themicro- and macro-typography is more tightly coupled by delaying the definite choice of line
breaks and instead offering to the pagination algorithm a set of options per paragraph modeled
as a flexible glue item. Using glue has the advantage that the complexity of the pagination
algorithm stays low compared to the approach outlined in this paper, but the disadvantage that
other aspects of the fully formatted paragraphs are unavailable to the pagination algorithm,
e.g., that for certain formatting the available breaks may be of different quality. Also if thepagination requests that a paragraph format itself to a certain height, say, 3.5 lines, it can only
fulfill that request to the nearest line number and as these errors accumulate, it is possible thatthe optimal solution is missed.
A quite different approach was taken by Piccoli et al. (2012) to provide the necessary flexibility
that enables a globally optimizing algorithm (they too use Knuth/Plass) to find solutions: They selectand combine prepared page templates to find an optimal distribution of text among the template
placeholders such that all pages are completely filled. The input text stream is split in chunks andeach chunk must completely fill into a template placeholder. Thus, the granularity of chunks will both
determine how huge the search space will get (and therefore how long it will take to find a solution)
and also how well the text gets distributed among the placeholders.

They then achieve filling the placeholders completely with text by manipulating the fontsize of the text for a consecutive set of placeholders that belong to what they call a flow, e.g.,
the text following a heading on a page. For a journal with many shorter articles that needs tobe assembled totally automatically, that approach may generate acceptable quality as longas the differences in text density stay really low and text that is experienced by the reader as
belonging together (e.g., from a single article) doesn’t show changes in density.
The authors have implemented their algorithm as an extension to a commercial environment, thus providing a complete production environment as the final rendering is left to
Adobe’s InDesign® that is provided with the selected template sequence and the text chunks
to be rendered as part of the template placeholders.
However, from a typographical perspective this approach is questionable, especially iftext is set in multiple columns as the human eye quite capable of spotting even very smallchanges in vertical sizes and density.4 This means that for continuous text such as novels thisis not an option if the intention is to produce high-quality results.
So why has no widely used production system, whether it be TEX or any other, started touse a global optimizing pagination algorithm up to now?
The answer is at least twofold: On one hand, due to the fact that pagination has todeal with unrelated input streams, the problems in this space are much harder than those inline breaking even though superficially they have a lot in common. As a result most of theresearch work so far has focused on experimenting with certain aspects only (with the possible
exception of the work carried out by Jacobs et al. (2003)) and was less concerned in providing
a production-ready solution initially. On the other hand typesetting requires much more thanpagination and any generally usable system implementing a new pagination either needs toalso provide all the features related to micro-typography (which is a huge undertaking) or itneeds to integrate into an existing system like TEX or any commercial engine.
On the commercial side, the complexity of full or even only partial optimization was so
far probably considered too high compared to any resulting benefits, and the open source TEX
system (while offering most aspects needed for high-quality typesetting5 ) is monolithic andso optimized for speed that it is very difficult to extend it or replace some of its algorithms.
4 There has been one paragraph set on this page with a font reduced by about 0.3mm but without changing the line spacing.
As a result that particular paragraph needs one line less—does it stand out? In my opinion it does, at least there is a slight queasy
feeling when looking at the page, even if you can’t immediately pinpoint the source.
5 For a discussion of T X’s limitations and failures see Mittelbach (1990) and for an update 23 years later Mittelbach (2013).
E

8

C OMPUTATIONAL I NTELLIGENCE

1.5. The main contributions provided by this paper
The current paper presents a framework for globally optimizing the paginations of
documents using flexible constraints that allow the implementation of typical typographic
rules. These can be weighted against each other to guide the algorithm towards a particular
desired outcome. In contrast to the prototypes discussed in literature it has the full microtypographic functionality of the TEX engine at its disposal and is thus able to typeset
documents of any complexity.
It uses an adaption of the line-breaking algorithm by Knuth and Plass (1981) which
is a natural approach also deployed by other researchers. However, due to the fact there islimited flexibility in pagination compared to line-breaking, a straight-forward adaptation of
the Knuth/Plass algorithm would not resolve the pagination problem: It provides a globally
optimizing algorithm, but one that runs out of alternatives to optimize in nearly all cases.
The other main contribution of this paper is therefore the extension of this algorithm toinclude two methods that add flexibility to the pagination process without compromisingtypographic quality and traditions. These are the support for:
Paragraph variants: Identification of paragraphs that can be typeset to different numbersof lines without much loss of quality, then using these variants as additional alternatives in
the optimizing process.
Spread variants: Support for page spreads (i.e., all columns of a double page) to be run
short or long, thereby increasing the number of alternatives for the algorithm to optimize.
Using both extensions enough flexibility is added to the pagination process that the globally
optimizing algorithm is able to find a solution for nearly any document in acceptable time
without running out of options.
1.6. The scope and restrictions of the framework
The framework is intended to support a wide variety of different applications but there
are, of course, some assumptions that restrict it in one or the other way.
It assumes that the input to the algorithm is a sequence of precomposed textual material,
intermixed with vertical spaces and that the task is to paginate this galley into columns
and pages of possibly different but predefined heights. In particular, this means that thehorizontal width of an object plays no role in the algorithm (everything has the same width).
As a consequence the framework cannot optimize designs that allow textual material to beformatted to choice of different widths.
The framework also assumes that the heights of columns used in pagination is known apriori and does not depend on the content of the textual material poured into it. It is therefore
not possible for the algorithm to balance textual material across several columns on a page
and then restart the flow on the same page as that would be equivalent to having variablecolumn heights that depend on signals from within the textual material.
The algorithm assumes that the textual flow is continuous and is placed into columns in
a predefined order. As implemented, the writing direction is top to bottom and left to right butother writing systems could be easily supported as that involves only a simple and straightforward transformation of the algorithm’s results prior to typesetting the final document.
Other than that, the framework poses no restrictions and supports all typical typographicaltasks using a system of user-specifiable constraints. In particular, it is possible to specify• whether or not columns need to be filled exactly (i.e., should align at the bottom);• the alignment of columns across a spread;• how much “extra” white space is considered acceptable in a column;• the management of micro-typographical features such as preventing “widows and orphans”
or hyphenation across columns, etc.;

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

9• the amount of paragraph length variations that is allowed;• the importance of conserving space, i.e., preferring less pages;• design criteria, such as a preference for headings to (always) start a new column;• requiring a full last page;6• any desirable or forced column breaks to affect the algorithm.
These user-specified requirements can be either absolute (in which case the algorithm will notconsider any solution that violates them) or they can be formulated as a preference, with thedifferent constraints weighted against each other according to user specification that indicate
their relative importance. This is done by attaching higher or lower cost values to individual
requirements. If even more granularity is needed for experimentation and research, then any
part of the objective function used for optimization can be easily adjusted.
As implemented, the framework is based on LuaTEX for reasons explained at the
beginning of Section 2. However, as the algorithm for determining the optimal pagination is
independent of the underlying typesetting system used, it would be possible to build a similar
framework with any other typesetting engine that is capable of generating the necessary
abstract representation of the galley as input for the algorithm (as discussed in Section 2.1.2).
The engine should also be able to format a paragraph to variable number of lines and measure
the quality of each formatting.7 Finally, it must be able to accept external directives whilst
paginating the final document (Section 2.1.4).
1.7. Downside of applying global optimization
While globally optimizing the pagination to further automate the typesetting process
sounds like a good idea, there are a number of issues related to it that need to be taken into
consideration and require further research.
First of all global optimization means that any modification in the document source canresult in pagination differences anywhere in the document. This is already now a source ofconcern for TEX users experiencing situations where deleting a word results in a paragraphgetting longer or being broken differently across columns. By optimizing the paginationsuch type of problems are moved from the localized level of micro-typography to the overall
document level—just consider a book revision where a few misspellings are corrected andinstead of regenerating a handful of photographic plates for these pages the publisher has togenerate a fully reformatted book.8
But there are also problems related to the interaction between globally optimized pagination and automatically generated (textual) content. If such generated content depends on thepagination, for example, if a text “see Figure 3 on the following page” changes to the much
shorter text “see Figure 3 on page 7”, then this generates feedback loops between micro- andmacro-typography, i.e., it might change the formatting, which might change the generated
text, which might change the formatting etc. It is not difficult given an arbitrary pagination
rule set, to construct a document for which there is no valid formatting possible under theconditions of this rule set. While such situations can already occur with pagination generated
by greedy algorithms, they are far more likely if global optimization (especially with variant
formatting for higher flexibility) is used.
6 Of course, if this is specified as a strict requirement then the algorithm may not be able to find any solution, depending on
the given input. A simple example would be a short document that simply doesn’t have enough material for a single page.
7 The algorithm is still capable of operating if the formatter is not capable of this, but the number of alternative solutions to
optimize will be greatly reduced. As shown in Section 4.7 this will often mean that documents have no solution that adheres tothe specified constraints.
8 The solution in that case, would be to introduce explicit pagination commands in strategic places to keep the pagination
unchanged, even if through the algorithm’s eyes it is no longer optimal.

10

C OMPUTATIONAL I NTELLIGENCE

2. A GLOBALLY OPTIMIZING FRAMEWORK USING TEXAs the open source program TEX by Don Knuth is undisputedly one of the best typesetting
systems in existence when it comes to micro-typography or math typesetting, it is a natural
candidate for any attempt to implement improved pagination algorithms as all other aspectsof typesetting are already provided with high quality and due to its large user base there are
immediately many people who could benefit from an improved program.
Unfortunately the original program by Knuth (986b) is of monolithic design and highly
optimized so that modifying its inner working has proven to be a serious challenge. There
have been a number of such attempts though and three of them have established themselvesin the world-wide community: pdfTEX is an engine written by Hàn Thê´ Thành (2000) as
part of his PhD thesis that was the first engine directly generating PDF output and it also
provided a number of micro-typography extensions, such as protrusion support and font
expansion (hz-algorithm). These days this TEX-extension has become the default engine inmost installations, i.e., the program being called, when people are processing a TEX file. The
other two (still more or less under active development) are XETEX (see, for example, Goossens(2010)) and LuaTEX, implemented by the LuaTEX development team (2017).
The interesting aspect of LuaTEX is that it combines the features of a complete (and infact extended) TEX engine with a full-fledged Lua interpreter that allows the execution of
Lua-code inside of TEX with full access to the internal TEX data structures and with the ability
to hook such Lua-code at various points into most TEX algorithms, enabling the code tomodify or even to replace them. As Lua is an interpreted language there is no need to compile
a new executable whenever some Lua code is modified; all it needs is the base LuaTEX engine
to be available (which is a standard engine in all major TEX distributions such as TEX Live).
As of fall 2016 LuaTEX has reached version 1.0, so the development activities are expected
to slow down with more focus on stability and compatibility compared to the situation in thepast. Thus, this version of LuaTEX can easily serve as a very versatile testbed for developing
algorithms that can be directly tried and used by a large user base. For this reason theframework described in this paper is based on LuaTEX.
2.1. High-level workflow
The framework presented here consists of four phases and uses LuaTEX for the reasons
outlined above. A high-level overview is given in Figure 3 showing the phases, their inputs
and outputs and the type of user-specifiable constraints that are applicable in the different
phases.
2.1.1. Phase 1 (preprocessing). The document, which consists of standard TEX files, isprocessed by a TEX engine without any modification until all implicit content (e.g., table ofcontents, bibliography, etc.) is generated and all cross-references are resolved.9 This implicit
content is stored in auxiliary files by TEX and reused as input in Phase 2 during the galley
generation and again in Phase 4 when producing the optimally paginated document.
2.1.2. Phase 2 (galley meta data generation). The engine is modified to interact with
TEX’s way of filling the main vertical list (from which, in an asynchronous way, TEX later
9 Cross-references to pages or columns in the final document can only be approximated at this stage as the final position in the
optimally paginated document is not yet known. We therefore use the values produced when paginating the document withstandard TEX (i.e., with a greedy pagination algorithm) as placeholders and hope that they are roughly the same width. They arethen replaced by the correct values in Phase 4. However, as explained in Section 1.7, documents with cross-references that
depend on the pagination may not allow valid formatting and may need a manual intervention that overwrites one or the otheroptimization criteria.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

11

F IGURE 3. High-level framework overview (Phases 1–4)
cuts column material for pagination). An overview about the workflow during that phase isshown in Figure 4 on the next page.
2.1.2.1. Engine modification when moving material to the galley in Phase 2
In particular, whenever TEX is ready to move new vertical material to the main verticallist this material is intercepted and analyzed. Information about each block (vertical height,
depth, stretchability if any and penalty of a breakpoint) is then gathered and written out to an
external file. In TEX, boxes (such as lines of text) have both a vertical height and a verticaldepth, which is the amount of material that appears below the baseline, e.g., the vertical sizeof descenders of letters such as “p” or “g”. The total vertical size of boxes is then the sum ofheight and depth. This distinction is important when filling columns with material, because
the depth of the last line must not be taken into consideration when determining the total
vertical size occupied by the material (while the depth of all other lines is). This reflects thefact that columns and pages should align on the baseline of the last text line regardless ofwhether or not such a line has descenders.

12

C OMPUTATIONAL I NTELLIGENCEF IGURE 4. Galley meta data generation (Phase 2)
If possible, data is accumulated, e.g., several objects in a row without any possibility forbreaking them up are written out as a single data point to reduce later processing complexity.
The modification is also able to interpret special flags (implemented as new types of“whatsit nodes” in TEX engine lingo) that can signal the start/end or switch of an explicit
variation in the input source. This information is then used to structure the corresponding datain the output file for later processing.10
2.1.2.2. Engine modification when generating paragraphs in Phase 2
The second modification to the engine is to intercept the generation of paragraphs targeted
for the main galley11 prior to TEX applying line breaking.
For each horizontal list that is passed to the line-breaking algorithm the framework
algorithm determines the possible variations in “looseness” within the specified parametersettings (galley constraints parameters). An example of a paragraph reformatted to a different
number of lines is shown in Figure 5 on the facing page.
10 This interface could be extended at a later stage to support controlling of the algorithm used in Phase 3 (pagination) fromwithin the document, e.g., to guide or overwrite its decisions locally.
11 Paragraph variations in other places, e.g., inside float boxes, marginal notes, footnotes, etc. are currently not considered.
Thus, those objects always have their natural (fixed) dimensions. Extending the framework in that direction would be possible
but would considerably complicate the mechanism without a lot of gain.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION’I won’t indeed!’ said Alice, in a great hurry
to change the subject of conversation. ’Are you–are you fond–of–of dogs?’ The Mouse did not
answer, so Alice went on eagerly: ’There is sucha nice little dog near our house I should like toshow you! A little bright-eyed terrier, you know,
with oh, such long curly brown hair! And it’ll
fetch things when you throw them, and it’ll sit
up and beg for its dinner, and all sorts of things–
I can’t remember half of them–and it belongs toa farmer, you know, and he says it’s so useful,it’s worth a hundred pounds! He says it kills all
the rats and–oh dear!’ cried Alice in a sorrowful
tone, ’I’m afraid I’ve offended it again!’ For the
Mouse was swimming away from her as hard as
it could go, and making quite a commotion in
the pool as it went.

optimal line breaks’I won’t indeed!’ said Alice, in a great hurry tochange the subject of conversation. ’Are you–are
you fond–of–of dogs?’ The Mouse did not answer,
so Alice went on eagerly: ’There is such a nice little dog near our house I should like to show you!
A little bright-eyed terrier, you know, with oh,such long curly brown hair! And it’ll fetch things
when you throw them, and it’ll sit up and beg forits dinner, and all sorts of things–I can’t remember half of them–and it belongs to a farmer, youknow, and he says it’s so useful, it’s worth a hundred pounds! He says it kills all the rats and–oh
dear!’ cried Alice in a sorrowful tone, ’I’m afraid
I’ve offended it again!’ For the Mouse was swimming away from her as hard as it could go, andmaking quite a commotion in the pool as it went.

run short (tight)

13’I won’t indeed!’ said Alice, in a great hurry
to change the subject of conversation. ’Are you–are you fond–of–of dogs?’ The Mouse did not
answer, so Alice went on eagerly: ’There is sucha nice little dog near our house I should liketo show you! A little bright-eyed terrier, youknow, with oh, such long curly brown hair!
And it’ll fetch things when you throw them,and it’ll sit up and beg for its dinner, andall sorts of things–I can’t remember half ofthem–and it belongs to a farmer, you know,
and he says it’s so useful, it’s worth a hundred pounds! He says it kills all the rats and–oh dear!’ cried Alice in a sorrowful tone, ’I’m
afraid I’ve offended it again!’ For the Mouse wasswimming away from her as hard as it could go,
and making quite a commotion in the pool as
it went.

’I won’t indeed!’ said Alice, in a great hurry
to change the subject of conversation. ’Are
you–are you fond–of–of dogs?’ The Mouse did
not answer, so Alice went on eagerly: ’Thereis such a nice little dog near our house I
should like to show you! A little bright-eyed
terrier, you know, with oh, such long curlybrown hair! And it’ll fetch things when you
throw them, and it’ll sit up and beg forits dinner, and all sorts of things–I can’t remember half of them–and it belongs to a
farmer, you know, and he says it’s so useful, it’s worth a hundred pounds! He says
it kills all the rats and–oh dear!’ cried Alice in a sorrowful tone, ’I’m afraid I’ve offended it again!’ For the Mouse was swimmingaway from her as hard as it could go, andmaking quite a commotion in the pool as it
went.

run long (loose)run very long—too loose!

looseness = 0

looseness = -1

looseness = 1

looseness = 2

tolerance = 4000

tolerance = 500

tolerance = 500

tolerance = 4000

Explanation: This paragraph from Alice in Wonderland is shown in in Figure 1 on page 4. For this paragraph the globally
optimizing pagination algorithm selected the variant with a looseness of -1 as shown in Figure 2 on page 5. The paragraphappears in the second column of page 5 in both figures.
In small column measures one should set the default tolerance fairly high (4000) to ensure that TEX finds a solution in situations
where line breaking is problematic. This particular paragraph, however, breaks nearly perfectly, thus a tolerance of 200 would
have produced the same result.
Trials with a non-zero looseness should use a smaller tolerance to avoid bad results when diverging from the optimum number oflines, e.g., with this paragraph two extra lines are only possible with a tolerance of 4000 or higher. With the standard constraint
settings this variant would therefore be considered a failure.

F IGURE 5. A paragraph from Alice under different looseness settings
For this the paragraph is first broken into lines according to the given h&j constraints resulting in a paragraph with ` lines. Then TEX is asked to try again and line-break the horizontal
list to generate paragraphs with lines between ` − min looseness and ` + max looseness.
For these attempts a special variation tolerance is used which can be set to a value
different from the paragraph tolerance used on normal paragraphs.
The paragraph tolerance defines whether or not lines are considered acceptable to be partof an optimal solution, thus with a higher tolerance TEX will have more possibilities to chosefrom. It will still use only lines with low tolerance if that leads to a solution, but it may notfind any solution at all if the tolerance is set too low and line-breaking is difficult (e.g., innarrow columns). Therefore allowing lines with high badness in emergencies might be better
than overfull lines, because no solution was found.
The situation with paragraph variants, however, is different: variants are intended toprovide some additional flexibility for the pagination process, but they should only be used
if their quality is sufficiently high. Therefore the line-breaking trial for variants should notconsider lines with high badness as acceptable, which means that the tolerance in these trials
should be set to a much lower value.
However, for positive values of looseness it is not enough to check if TEX could build aparagraph matching it, as TEX by default uses a fairly naive approach that would always resultin the last line containing only a single word or even only part of a single word whenever theparagraph is lengthened.
It is therefore important to first manipulate the horizontal material to prevent this fromhappening and ensure that “loosened” paragraphs stay visually acceptable to the human eye.12
The approach is to add extra penalties to the line break possibilities near the end of theparagraph (including those due to hyphenation), so that TEX will prefer to break elsewhere
unless there is no good alternative. Thus, if feasible TEX will put at least a few words into
12 As the paragraph variations with this manipulation applied are used as input to the optimizing algorithm used in Phase 3,

we will later have to re-apply the manipulation in exactly the same way in Phase 4 (typesetting) on any variant paragraph thathas been chosen in Phase 3 as being part of the optimal solution to ensure that it is typeset accurately.

14

C OMPUTATIONAL I NTELLIGENCE

the last line. The behavior can be observed in Figure 5 where the loose setting still has twowords on the last line, but the very loose setting ends with a single word, because otherwise
the paragraph would have been even worse.
For each possible variation the paragraph breaking trial then determines the exact sequenceof lines, vertical spaces and associated penalties under that specific “looseness” value.
Such trials with a special looseness may fail, either because the requested loosenesscannot be attained at all, or only with a tolerance value exceeding the variation tolerance
constraint, or because the resulting paragraph has overfull lines (like this one).
Solutions with overfull lines can happen because the trials are typeset with a special
tolerance value. Under this tolerance the paragraph may not have any acceptable solution (i.e.,
without overfull lines). Starting from such a “bad” paragraph breaking as the best possibility,
TEX might report success in making it even shorter because that doesn’t make it worse in
TEX’s eyes (i.e., they are considered to be equally bad).13
The results of each successful trial are then externally recorded together with theassociated “looseness” value of that variation. For a given looseness value the line-breaking
chosen by TEX will be optimal (Knuth, 986a, p. 103), but of course it will usually be of alower quality compared to the optimal line-breaking with ` lines (i.e., the number of lines
with looseness 0). The algorithm accounts for this by applying a user-customizable cost factor
whenever such a variant is chosen in Phase 3 below.
Finally, instead of adding a vertical list representing the formatted paragraph on TEX’s
main vertical list, the material is dropped and a single special node is passed so that theparagraph material is not collected again by the first modification described above.
As already indicated, the user-specifiable constraints used in in this phase are thosedealing with the break costs during h&j (e.g., handling of widows and orphans, breaks before
headings etc.), specifications of flexible vertical spaces (e.g., skips between paragraphs, before
headings, around lists, etc.) and the galley variation constraints that describe what kind ofparagraph variations are deemed acceptable and what additional costs to add if a variation
with a lower paragraph quality is chosen.
As the result of this phase the external file will hold an abstraction of the document
galley material (the galley object model in Figure 4) including marked up variations for eachparagraph for which valid variations exist.
2.1.3. Phase 3 (determining the optimal pagination). The result of Phase 2 (i.e., thegalley object model) is then used as input to a global optimizing algorithm modeled after
the Knuth/Plass algorithm for line breaking that uses dynamic programming to determine an
optimal sequence of column and page breaks throughout the whole document. Compared to
the line-breaking algorithm this page-breaking algorithm provides the following additionalfeatures:• Support for variations within the input: This is used to automatically manage variant break
sequences resulting from different paragraph breakings calculated in Phase 2, but could
also be used to support, for example, variations of figures or tables in different sizes orsimilar applications.
• Support for shortening or lengthening the vertical height of double spreads to enable better
column/page breaks across the whole document.
• Global optimization is guided by parameters that allow a document designer to balance theimportance of individual aspects (e.g., avoiding widows against changing the spread heightor using sub-optimal paragraphs) against each other.
13 This behavior caused some surprise during the implementation of the algorithm until it was understood that an explicit
check for overfull lines is needed at this point.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

15

F IGURE 6. Generate the optimally paginated document (Phase 4)
The influence of such user-specified constraints is discussed in Section 3; details of thealgorithm are then described in Section 4.
The result of this phase will be a sequence of optimal column break positions within the
input together with length information for all columns for which it applies. Also recorded iswhich of the variants have been chosen when selecting the optimal sequence.
2.1.4. Phase 4 (typesetting). This phase again uses a modified TEX engine that is capableof interpreting and using the results of the previous phases. For this it hooks into the sameplaces as the modifications in Phase 2, but this time applying different actions (see Figure 6).
To begin with, the vertical target size for gathering a complete column will be artificially
set to the largest legal dimension so that by itself the TEX algorithm will not mistakenly breakup the galley at an unwanted place due to some unusual combination of data.14
14 As long as the calculation for deciding on a column break used by T X and the one used by the algorithm deployed inE
Phase 3 are exactly the same this is actually not necessary. However, requiring a 100% correspondence is not a useful restriction,
so this is a safety measure against deliberate or unintentional differences in this place.

16

C OMPUTATIONAL I NTELLIGENCE

2.1.4.1. Engine modification when generating paragraphs in Phase 4
Whenever TEX gets ready to apply line breaking to paragraph material for the main
vertical list the modification looks up with which “looseness” this paragraph should be typeset
and adjusts the necessary parameters so that TEX generates the lines corresponding to thevariation selected in the optimal break sequence for the whole document determined inPhase 3 (pagination). At this point the algorithm also re-applies the modification described in
Section 2.1.2.2 page 13 on any paragraph for which a variation was chosen.
2.1.4.2. Engine modification when moving material to the galley in Phase 4
While TEX is moving objects to the main vertical list the algorithm keeps track of thegalley blocks seen so far and when it is time for a column break according to the optimal
solution it will explicitly place a suitable forcing penalty onto the main vertical list so that
TEX is guaranteed to use this place to end the current column or page. Again as a safetymeasure other penalties seen at this point that should not result in a column break will beeither dropped or otherwise rendered harmless so that TEX’s internal (greedy) page-breaking
algorithm is not misinterpreting them as a “best break” by mistake.
Finally, whenever TEX has finished a column (due to the fact that we have added an
explicit penalty in the previous step) we will arrange for the correct target dimensions for thecurrent column according to the data from Phase 3 (pagination). This is done immediately
after TEX has decided what part of the galley it will pack up for use in its “output routine”(which is a set of TEX macros) but before this routine is actually called.15
The result is a paginated document with globally optimized column breaks according to
the user-specified constraints.
2.2. Notes on the workflow phases
The Phase 1 (preprocessing 2.1.1) is necessary to generate all implicit content so that
it will be considered in the following phases. Without this phase the page-breaking step inPhase 3 would base its evaluation on wrong input.
Phases 2 (galley generation 2.1.2) and 4 (typesetting 2.1.4) will require a modified/extended TEX engine. The workflow uses the LuaTEX engine for this purpose as it internallyprovides a Lua interpreter to implement the modifications as well as the necessary callbacks
into the TEX algorithms so that the new code can easily take control and provide the necessarychanges.
The algorithm used in Phase 3 (pagination 2.1.3) is also implemented in Lua. As thisphase is executed without any direct involvement of a TEX engine processing the source
document, this code could have been written in any computer language (and could probably
be faster, depending on language choice and implementation). Nevertheless, the use of Lua
was deliberate, as it allows to use the LuaTEX engine16 in all phases and this means that theworkflow can be executed using a standard TEX installation, i.e., is out of the box available
for the millions of LATEX-users and other TEX flavors without the need to install any additional
software programs.17
While the typesetting phase (Phase 4 2.1.4) claims that the result is a globally optimized
formatted document, it doesn’t actually claim that it is a correctly formatted document andas explained in Section 1.7 this may in fact not be the case. The mechanisms available in
15 This way the engine modifications are largely transparent for the T X macro level and the modification will work withE
some small adjustments with any macro flavor of TEX, e.g., LATEX, plain TEX, etc.
16 LuaT X can be run as a standalone Lua interpreter by calling it under the name texlua.
E
17 Lua code is interpreted and available in form of ASCII files. It can therefore be easily provided as part of the standard T X
E
distributions or (with older installations) manually downloaded and installed.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

17

LATEX will detect this situation, but the framework currently makes no attempt to resolve thisproblem if it arises. Depending on the exact nature of the issue a further run through Phases
2–4 might resolve it. However, if the formatted result oscillates between two or more statesthen manual intervention is necessary.
As indicated in Figure 3 the behavior of the framework is customizable through parameterization during all four phases. The next sections will show that more complex customizations
can be carried out as well, by providing alternative code written in Lua that modifies theframework algorithms.
3. THE CONSTRAINT MODEL USED FOR GLOBALLY OPTIMIZEDPAGINATIONIn this section we discuss the constraints necessary to implement common and lesscommon typographic design criteria for pagination. In part, these are already provided
by TEX (though used there by its greedy pagination algorithm and not in the context ofglobal optimization). Additional ones are added for exclusive use by the globally optimizing
pagination algorithm discussed in Section 4.
A number of user-specified constraints available as parameters of the TEX engine define
the set B of breakpoints available in a given document galley as well as the numerical “costs”
associated with such breakpoints (see Section 3.1). With P we denote the set of all partitionsof the galley along such breakpoints, i.e., the set of all subsets of B.
Further user-specifiable constraints are implemented by defining a suitable objectivefunction F that numerically measures the “inverse quality” (lower values are better) of apartition p = {b0 , . . . , bn } ∈ P, i.e., how well p adheres to the given constraints. By attachingdifferent weights or using different formulas in the the objective function or when calculating
the breakpoint costs it is possible to adjust the relationships between different (possibly
conflicting) constraints and favor some over others. Some examples are given below.
Thus abstractly speaking the act of globally optimizing the pagination of a galley means
finding a p ∈ P for which F (p) is minimal. Doing this by evaluating F (p) for every possible
partition is impractical as most of the partitions will result in an impossible or ridiculously
bad pagination (i.e., with overfull or nearly empty columns). Furthermore, the number ofpartitions grows exponentially in the number of breakpoints so that even for small galleys
the number of cases to evaluate will exceed the capabilities of any computer. It is therefore
important to reduce number of evaluations significantly while still ensuring thatmin F (p)p∈P

(1)

will be found. As we will see this problem can be solved with dynamic programming
techniques as long as the objective function has certain characteristics.
3.1. Constraining the available breakpoints
TEX already provides a sophisticated breakpoint model to describe different typographic
requirements. In TEX it is used to guide its greedy pagination algorithm but clearly all ofthese constraints make sense for a globally optimizing algorithm as well, so we use thoseunchanged. The breakpoints of a galley are modeled in TEX as follows:• Breaks are implicitly possible in front of vertical spaces if such spaces directly follow a box(e.g., a line of text). Such breaks are normally neutral, i.e., have no special cost associatedwith them (though there is a parameter to change that). As lines of a paragraph are always
separated by spaces (to make them line up at a distance of a “baselineskip”) this means that
it is usually possible to break after each line of text.

18

C OMPUTATIONAL I NTELLIGENCE• Breaks are also possible at so-called penalty nodes that can be explicitly added throughmacros (such as a heading command) or implicitly by TEX through parameters in certain
situations. The value of the penalty defines the “cost” to break at this point: A negativevalue means there is an incentive to break here and a positive value means a break at thispoint is less desirable.
• However, a value of 10000 or higher means a break is totally forbidden, thus by adding apenalty with that value a break at a certain point can be prevented.
• In the opposite direction a value of −10000 or less means that a break is forced, i.e., TEX
will always break at this point.
• A number of typographical conventions are modeled by TEX through parameters thatgenerate penalty nodes, e.g., between the first and second line of a paragraph TEX adds apenalty with the value of \clubpenalty (to model orphans) and between the last andthe second last it adds a penalty of \widowpenalty. If a line ends in a hyphen it adds
\brokenpenalty, etc.
Thus, by setting such penalty parameters to appropriate values, certain breakpoints can bemade more or less attractive (or can be totally forbidden). For example, LATEX by default
adds a penalty of −300 in front of a section heading, thus breaking in front of headings
is encouraged. In the opposite directions widows and orphans are frowned upon therefore\widowpenalty and \clubpenalty have a default value of 150 and many journal
designs even require 10000, i.e., totally forbid orphans and widows.
3.2. Constraining the column “badness”
As mentioned in the introduction one quality factor for a good pagination is the whitespace distribution in the columns, i.e., how far this distribution deviates from the optimal
distribution as specified by the design for the document. If every vertical space s in a document
has a natural height Hs and an acceptable18 stretch Ss+ and shrink Ss− , then it is possible todefine a function that calculates a “badness” for a column that contains a certain amount ofmaterial.
Intuitively speaking that badness should be 0 if all spaces in the column are set exactly
to their natural height and it should increase if the spaces have to be stretched or need to becompressed to fit all material into the column. Compression beyond a certain amount should
not be possible (to avoid overlapping material in the column), thus a natural limit would be
disallowing more than the available shrink.
Stretching beyond the available stretch amount is certainly also undesirable. However,experiments show that with many documents it is not possible to find any solution at all if
the allowed space distribution is handled too rigidly. A practical badness function should
therefore penalize such loose columns heavily, but not totally disallow them.
The badness function used by default in the algorithm outlined in this paper is given by
if there is infinite stretch within hmateriali
0badness(hmateriali) = ∞(2)
for r < −1, i.e., column is overfull
col i
100|r|3 for r > −1
where r is the ratio of “space needed to fill column i” and stretch available, i.e., ∑s Ss+ (incase of stretching) or the ratio of “shrink amount necessary to fit the material into column i”
and the shrink available, i.e., ∑s Ss− . If stretching or shrinking is required but no stretch or
shrink available we set r = ∞, thus the badness too will become ∞ in the above formula.
18 Acceptable, in the eyes of the designer of the particular document design.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

19

The precise form of the badness formula in equation (2) is admittedly an arbitrarychoice,19 but due to its cubic form it does penalize larger deviations from the desired state morestrongly and thus models the general expectation quite well. Nevertheless, experimenting withdifferent functions to see how that influences the algorithm behavior could be an interesting
study in itself. This is supported by the framework by providing the badness function as auser-redefinable Lua function.
With a badness function like the one given in (2) we can specify a customizable constraint that drops inadequate solutions by defining a constant ctolerance such that any solution
containing a column with a badness higher than ctolerance is rejected.
Thus, if p = {b0 , . . . , bn } is a partition of the document into n columns (with b0 and bn
the document start and end, respectively, and the other bi the chosen breakpoints) and if ci isthe cost associated with breakpoint bi we can define a simple objective function F as follows:n badness(b , b ) + c if ∀i : badness(b , b ) 6 ci−1 i
tolerance∑ col i i−1 i i
col i
F (p) = i=1(3)∞otherwise
The above objective function can be improved in several directions. In its current form it does
not distinguish solutions with different numbers of columns if the additional columns havebadness and break costs both zero or canceling each other. However, minimizing the numberof columns is an often required constraint. It also has the disadvantage of favoring solutions
with a few really bad columns or really high costs over an overall lower badness and cost—in
other words it is not minimizing the overall badness and cost values at all.
The first problem can be resolved by adding a customizable ccolumn penalty that will be
added for each column, i.e., n times and the second problem by doing the summation oversquares or cubes of the badness and costs.
Thus an improved definition for F is given by

F (p) =n δif ∀i : badness(bi−1 , bi ) 6 ctolerance

i=1∞

otherwise

∑ i

col i

(4)

with

δi = ccolumn +


2



badness(bi−1 , bi ) + c2i


col i


2

badness(bi−1 , bi ) − c2i

col i



2




 badness(bi−1 , bi )col ifor ci > 0
for −10000 < ci < 0otherwise (forced break)

Just like the badness function in equation (2) the above objective function is only one possible
way to constrain the solution space, but one that has proven to produce high-quality results
by providing a good balance between trying to minimize the badness over all columns while
putting also some weight onto a certain level of uniformity across all columns.
The influence of column badness compared to the influence of the break costs could
be adjusted by changing either definitions in (2) or (4) or changing the cost values for theindividual breakpoints, with the latter being the most flexible approach.
19 Modeled after the badness function used by T X to define the badness of lines in line breaking and the badness of pages
E
when deciding where its greedy algorithm should cut the next page.

20

C OMPUTATIONAL I NTELLIGENCE

3.3. Constraining the use of paragraph variations
For the paragraph variation extension we provide user constraints for defining the rangeof variations that are tried (min looseness and max looseness) and the minimal quality
all lines of a variant paragraph must have (variation tolerance) to be considered at all.
To find the optimal line breaking for a paragraph TEX calculates a numerical cost value foreach possible line breaking. For each of the variations this cost value will be obviously higher
than the one calculated for the optimal result. Thus, we can use the difference ∆ between
the two and add it (multiplied with a user-customizable factor cpara variation ) to the column
costs if a particular variant paragraph is being used in the pagination solution. This factor
then allows the user to specify how much the algorithm should disfavor solutions that use
paragraph variants, i.e., diverge from the optimal micro-typographic solutions when searchingfor a suitable pagination.
To incorporate the paragraph variation extension into the objective function F we haveto add in another term that sums up the additional costs generated in each column due toselecting paragraph variants instead of the optimal paragraphs.
Thus, a suitable form that includes this extension would take the following form:nn ∑ δi + ∑ αi
if ∀i : badness(bi−1 , bi ) 6 ctolerance
col i
i=1
F (p) = i=1
(5)


∞
otherwisewith
αi = cpara variation

·

∑

∆

(the ∆ values depend on the para variations!)

para variations
used in col i

3.4. Constraining the use of spread variations
For the double spread variation we provide cspread variation as a user-specifiable constant topenalize running a column long or short. Note that with the spread variation we introduce a
dependency between columns as for typographical reasons all columns of a spread should
be handled in the same way. That is, the first spread has only one page while all the laterones have 2 pages. Thus, if each page has k columns and we denote by σ = {σ1 , . . . , σn }the modifications we make to each column, then we have σ1 = · · · = σk , σk+1 = · · · = σ3k ,σ3k+1 = · · · = σ5k , etc.
The objective function from (4) can then be augmented to cover both extensions asfollows (note that F now takes both p and σ as input):n ∑ (δi + αi + γi )if ∀i : badness(bi−1 , bi ) 6 ctolerancecol i
F (p, σ) = i=1
(6)


∞
otherwise
with

γi =

cspread variation0

if σi 6= 0 (short or long spread)otherwise

More complex definitions for γi are possible, for example, by providing different constraints for long and short spreads and by adding some extra costs if the sequence changes

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

directly from long to short or vice versa, e.g., a definition such ascshort spread if σi < 0 (short spread)γi = cincompatible spread · (|σi − σi−1 | − 1) + |σi | · clong spread if σi > 0 (long spread)0otherwise

21(7)

However, at the moment the algorithm described in Section 4 uses the simpler definition fromequation (6).
3.5. Finding the minimum F (p, σ)As mentioned above, given m breakpoints in a galley we have a total of 2m possible
partitions in P to consider. This makes a simple enumeration approach therefore clearly
intractable. However, as long as the objective function used has certain characteristics we will
see that the problem can be solved efficiently though dynamic programming techniques.
To successfully apply dynamic programming we need to be able to formulate the problem
as a number of subproblems that share common subsubproblems, and it is necessary thatthe problem exhibits optimal substructure. By this we mean that an optimal solution to the
problem consists of optimal solutions to its subproblems.
By solving the common subsubproblems only once and remembering an optimal solution
for them we can successively build optimal solutions to larger subproblems as due to the
optimal substructure we know that an optimal solution to a subproblem will only contain
optimal subsubproblems. Thus we do not have to remember any of the non-optimal solutions
to subsubproblems, thereby considerably reducing the solution space to evaluate.
If we look at the pagination problem of finding p ∈ P with minimal F (p, σ) for somegiven σ we can easily see that it can be formulated as a problem with overlapping subproblems
and that with an objective function like the one given in equation (6) it exhibits optimal
substructure.
Assuming each page has k columns and given a partition p = {b0 , . . . , bn } and a spreadvariation sequence σ = {σ1 , . . . , σn } then this partition will generate s = b(n − 1 + k)/2kc + 1
spreads the last one possibly not fully filled with columns. If we denote by n0 the column
number of the last column in the second-last spread, i.e., n0 = (2(s − 1) − 1)k then p0 ={b0 , . . . , bn0 } defines a sub-partition of p that generates all but the last spread.
Now we havenF (p, σ) = ∑ (δi + αi + γi )
i=1
n0

n

= ∑ (δi + αi + γi ) +i=1= F (p0 , σ 0 ) +∑ (δi + αi + γi )i=n0 +1n∑ (δi + αi + γi )(8)

i=n0 +1

where σ 0 = {σ1 , . . . , , σn0 }. The sum ∑ni=n0 +1 (δi + αi + γi ) can be thought of the extra costs
added by the columns in the last spread. Now the term δi in this sum is independent of the
breakpoints in p0 and the spread variations σ 0 of the first spreads (it depends on σn0 +1 = · · · =σn though). The paragraph variation term αi always depends only on the situation in column iand the term γi for the columns of the last spread is independent of σ 0 as we have made thesplit after the last column of a spread.

22

C OMPUTATIONAL I NTELLIGENCE

Thus, if p is an optimal solution for paginating the document into n columns under a given
spread variation σ, then p0 must be an optimal solution for paginating the partial documentfrom b0 to bn0 , i.e., into s fully filled spreads. If p0 would not be optimal we could replace itwith an optimal pagination p00 , i.e., one with F (p00 , σ 0 ) < F (p0 , σ 0 ) which would contradictthat F (p, σ) is minimal.
By the same argument we can see that F (p0 , σ 0 ) is in fact an optimal solution regardlessof the chosen spread variations, i.e., replacing σ 0 by some other σ 00 cannot improve the result.
However, this argument only works if we choose the simpler definition for γi from equation(6). If we use the definition from (7) instead, then the γi from the columns of the last spread
have a dependency on σn0 which is part of F (p0 , σ 0 ). Thus in that case an algorithm would
need to work harder and keep more of the potential partial solutions in memory.
On the other hand if we keep σ fixed then the above argument is true for any value of n0
as then the terms in the right hand sum are always independent of F (p0 , σ 0 ).
To find the optimal solution it is therefore sufficient to first find all breakpoints that canend the first column within the given constraints and all possible values for σ1 . Then startingfrom those breakpoints find all breakpoints that provide a solution to end the second column
using σ1 = σ2 . This continues until we reach the end of a spread in which case we only needto remember the best way to reach this point, i.e., the one with F (b0 , . . . , bn0 , σ) for any σ
because of equation (8).
Then the process reiterates, trying all possible values for σn0 +1 as we are at the start of a
new spread. This continues until we finally reach the end of the document with bn as our last
breakpoint. This breakpoint may have been reached several times using different values for σnand the optimal solution for the pagination of the whole document is then simply the sequenceof breakpoints through which we reached that last breakpoint with minimal F ; somethingthat can be easily obtained by backtracking through the partial solutions remembered along
the way.
As we will see below this approach will result in an algorithm that has a quadratic runtime
behavior in the number of breakpoints; in fact, if all columns have the same height, it will
even run in linear time.
4. AN ALGORITHM FOR GLOBALLY OPTIMIZED PAGINATIONIn the following we discuss a slightly simplified version of the algorithms used in thepagination phase (Phase 3) of the framework. As mentioned before the base algorithm is avariation of the Knuth/Plass algorithm for line breaking suitably changed and adjusted for thepagination application. In particular it uses a somewhat different object model to account forthe pagination peculiarities and to support the extensions.
On a very high level of abstraction, one can build an object correspondence between
the algorithms as follows: Words in Knuth/Plass correspond to paragraphs in pagination;
hyphenation points in words to lines that allow column breaks; spaces between words to(stretchable) vertical spaces between paragraphs or other objects on the galley. However,while words or partial words have only a width that is used by the Knuth/Plass algorithm,
objects for the pagination algorithm have both a height and a depth as we see later and bothneed to be separately accounted for.
While the double spread extension (Section 4.4) has no natural application in line breaking,the variation support extension (Section 4.5) could be incorporated back into a line-breaking
algorithm: Individual variation paths would become alternate words or phrases and a global
optimizing line-breaker would then pick and choose among them, to best satisfy otherrequirements, such as desired number of lines, number of hyphenated words, tightness ofwhite-space, etc. This would, for example, support and simplify the approach outlined by
Kido et al. (2015) on layout improvements through automated paraphrasing.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

23

4.1. Preliminary definitions
The input for the pagination algorithm is the galley object model generated in Phase 2.
This is a sequence of objects x1 , x2 , . . . , xm where each xi is either a “text” block ti that will always be present in the final paginated document (e.g., textual material) or a “breakpoint/space”
block bi at which the galley may get split during pagination.
Usually a text block represents a single line of text in the galley. However, if there is nolegal breakpoint between two or more lines, then all such lines and any intermediate spaces
are combined by the process in Phase 2 into a single text block. For example, if widows andorphans are disallowed, then a three-line paragraph would have no legal breakpoint and thus
would form a single block. Other examples are multi-line equations or code fragments thatare marked as unbreakable in the source.
In a similar fashion consecutive vertical spaces in the source will be combined into asingle breakpoint block as the galley can only be broken in front of the first of such spaces.
If, however, a space in the source is followed by an (explicit) penalty, then this starts a new
breakpoint block to represent the additional breakpoint. Thus, without loss of generality, we
can assume that the block sequence alternates between single text blocks and one or moreconsecutive breakpoint blocks.
If a break happens at bi then that block gets discarded (in particular it doesn’t contributeto the height of the columns on either side of the break).20 In addition all directly following
breakpoint blocks bi+1 , bi+2 , . . . will also be discarded. This reflects the fact that spaces
between textual elements are expected to “vanish” at column/page breaks.
Each block xi has an associated height Hxi , stretch Sx+i and shrink Sx−i component that
describe the block’s contribution to the galley and in case of breakpoint blocks also an
associated penalty Pbi , indicating the cost of breaking at this block.
Additionally, each text block ti has an associated depth component Dti that holds the sizeof the descenders in the last line of the block. This value is not directly incorporated into the
Hti as it should not participate in height calculations if ti is the last block before a break as
explained earlier. For breakpoint blocks Dbi is always 0.
For any i < j we define coli, j to be the material between the two breakpoints bi and b ji.e., the sequence of all blocks xafter(i) , . . . , x j−1 where xafter(i) is the first text block with anindex greater than i (as all breakpoint blocks directly following a break are dropped). We callthis a “column candidate” as it may be the material that gets placed into a column by thealgorithm. The natural height of its content isj−2

Hcoli, j =∑(Hxk + Dxk ) + Hx j−1 ,(9)k=after(i)j−1−+
its depth is Dcoli, j = Dx j−1 , its stretch is Scol= ∑k=after(i)Sx+k and its shrink Scolis defined
i, j
i, j
in the same way.
If Ck is the target height for column k in the final document, then we denote by Qki, j thecost value (the inverse quality, i.e., lower values mean higher quality) calculated for placing
the material coli, j into column k. Its definition is given by(−∞if Hcoli, j − Scol
> Ck
i, j
Qki, j =(10)−+
f (Ck , Hcoli, j , Scoli, j , Scoli, j , Pb j ) otherwise

If there is no way to squeeze the material into the available space (i.e., when the column isoverfull after applying all available shrink) we have Qki, j = ∞. Otherwise the function f is
20 In the remainder of the paper we therefore usually talk about “the breakpoint b” rather than “the breakpoint at breakpoint
block b” if there is no confusion possible.

24

C OMPUTATIONAL I NTELLIGENCE

used to provide a measure for how well the content sequence fills the column, e.g., how muchspace is left unused. For its precise definition many possibilities are available, provided thefunction has no dependencies on breakpoint choices made earlier, or if it does, only needs tolook back through a fixed number of earlier breakpoints to ensure applicability for dynamic
programming. By default the framework currently uses the “badness” function that is also
used by TEX’s greedy algorithm for page breaking, i.e., the badness function discussed in
Section 3.2, i.e.,(−∞ if Hcoli, j − Scol
> Ck
k
i, j
Qi, j =
(11)
δk otherwise
However, this could be altered and made more flexible.
If badnesscol k (bi , b j ) 6 ctolerance for some customizable parameter ctolerance we call coli, ja feasible solution for column k in the final document (or, if all columns have the same target
height, a feasible solution for all columns) otherwise an infeasible one that we ignore.21
The goal of the algorithm can now be formulated as the quest to find the best sequence of
breakpoints b0 , b2 , . . . , bn through the document such that all Qkbk−1 ,bk are feasible andn

Db0 ,...,bn = ∑ Q`b`−1 ,b`

(12)

`=1

is minimized (with b0 and bn representing start and finish of the document, respectively). In
the TEX world D is usually called the demerits of the solution.
To solve this, it is not necessary to calculate Qki, j for all possible combinations of k, i andj because Qki, j = ∞ implies Qki, j+1 = ∞. Furthermore, if b0 , . . . , bk and b0 , b01 , . . . , b0k−1 , bk are
two breakpoint sequences ending at the same place, the algorithm only needs to remember
the best of the two partial solutions, because extending the sequences to bk+1 means adding
Qk+1
bk ,bk+1 so the relationship between the extended sequences will stay the same.
The algorithm therefore loops through the sequence of all xi thereby building up all
partial breakpoint sequences b0 , . . . , bk that are possible candidates for the best sequences,i.e., applying the pruning possibilities outlined above. For this we maintain a list active nodes
A = a1 , a2 , . . . where each ai is a data structure that represents the last breakpoint bk in somecandidate sequence plus some additional data.22 This list is initialized with a single active
node representing the document start.
While looping through xi we maintain information about total height, stretch and shrink
from the start of the document up to xi . In the data structure for an active node a we record
the column number k that ended in this node and the total height, stretch and shrink from thestart of the document to bafter(a) so that calculating, for example, Hcola,b j becomes a simple
matter of subtracting the total height recorded in a from the total height at b j .
Da is defined to be the smallest demerits value that leads up to a break at a, i.e., Da =Db0 ,...,bk for some sequence of k + 1 breakpoints with break(a) = bk . Recording this value
in the active node data structure for a makes it easy to prune those active nodes that cannot
become part of the final solution and to arrive at equation (12) eventually, as we have0Da0 = Da + Qk+1
bk ,bk+1 for a newly created active node a at breakpoint bk+1 .
Whenever we encounter new possible candidate sequences we compare them and add
corresponding active nodes for the best of them. And when an active node a is so far away
21 There are cases where it is necessary to consider infeasible solutions as well but these are boundary cases that we ignore forthe discussion here.
22 Again it is convenient later on to talk about “the breakpoint a” instead of “the breakpoint b that is associated with the active
node a” if there is no possible confusion.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

25

from the current block xi such that Qk+1
a,xi = ∞ we remove the active node from the list as thepartial sequence represented by a can no longer be extended to become the best solution.
4.2. Details of the base algorithm
The overall algorithm is detailed out in Figure 7 and works as follows: We start byinitializing the active list with a single node representing the start of the document. Fori = 1, . . . , m, i.e., all blocks in the galley model, we then do:
Case xi = ti : We update the totals seen so far by adding Hti , St+i and St−i , respectively. The
depth Dti is not yet added at this point.
Case xi = bi : A possible breakpoint; the detailed workflow for that case is shown in Figure 8.
We loop through all active nodes a ∈ A and evaluate
β = badness (a, bi )column(a)+1

using the badness function from (2) to see how well it works to form the column column(a)+1 with the material between a and bi , i.e., with cola,bi .
If β 6 ctolerance we remember cola,bi as one feasible way to end column column(a) + 1 atbreakpoint bi .
Otherwise, if ctolerance < β < ∞ we consider cola,bi an infeasible way to end the columnthat we normally ignore.23 By suitably ordering the active nodes we can ensure that all
further active nodes will also have ctolerance < β .
This is achieved by grouping all active nodes of the same column class24 together andwithin each group ordering the active nodes by their distance from the start of the
document (earlier ones first). Given a badness function as the one defined by (2) thismeans, that if the material that is put into the column is already been stretched out, thebadness will get worse if we put less material in.
Thus, as long as Pbi is not a forced break and we are already stretching we do not needto consider any further active node in the current column class as it will have a worse
badness. This will speed up the algorithm considerably especially if there is only a single
column class.
Otherwise, if β = ∞ we remove the active node a as it is too far away from bi and can’t
form a feasible solution with this or any later breakpoint.
In either case, if Pbi is a forced break we also remove the active node a as it cannot form acolumn with a later breakpoint. Because of this necessary housekeeping we can’t end
the loop prematurely in case of forced breaks.
Then we move to the next active node unless the loop ended prematurely above in whichcase we move to the first active node in the next column class if any.
Once all active nodes are processed we determine bafter(i) so that the total height, stretch
and shrink from the beginning of the document to this breakpoint can be calculated for any
newly created active nodes associated with bi .
We then look at all the newly collected candidate solutions ending in bi and for eachdifferent column k we select the best candidate (having the smallest value of ∑k`=1 Q) andrecord a new active node for it. Infeasible candidate solutions with ctolerance < β 6 ∞ will
23 Exception: If the current break is forced and we haven’t seen a feasible solution so far, we need to keep the best of theinfeasible ones, as otherwise the active list would be empty afterwards.
24 Abstractly speaking, a column class is defined by the sequence of heights for all future columns that still need to be built.
Thus, if all column heights are equal there is only one column class. Otherwise, if two active nodes end different columns, theircolumn class will usually be different. In case of double spread support the column class may even differ if the active nodes end
the same column (since the following column may be run short or long, i.e., differ in height).

26

C OMPUTATIONAL I NTELLIGENCEF IGURE 7. The main algorithm (Phase 3)
Activities when encountering a break block are further detailed in Figure 8 on the next page. Generating
new active nodes with or without double spread support is outlined in Figure 9 on page 29. Finally, thehandling of paragraph variations is further detailed in Figure 10 on page 31.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

27

F IGURE 8. Handle a break block (Phase 3)
normally be thrown away at this point unless they are the only way to proceed, i.e., if
without one of them the active list would end up being empty.
Finally we update the totals seen so far by adding the new height and the previous depth(Hbi + Dxi−1 ), and the stretch and shrink Sb+i and Sb−i . This has to happen after generating
new active nodes as the material is not part of the current column if a break is taken at bi .
Finally, after having processed xm which is the last node in the document and supposed to
be a forcing breakpoint, we have only active nodes left that correspond to xm (but possibly
to different columns/pages). Out of those we select the one with the smallest Da as the bestsolution. From this active node we can move backwards through the active nodes that lead toit, to obtain the complete breakpoint sequence of the optimal solution.25
4.3. Complexity and search space
In the algorithm as described the cost function Q that weights the different constraints
against each other is used to obtain the final solution (by minimizing ∑ Q) but to limit the
search space only the status with respect to the column badness is evaluated. This means thatsolutions with a column badness higher than ctolerance are disregarded even if their Q-value
may be lower than others that are being considered.
One can informally describe this a behavior as follows: Different constraints can beweighted against each other but only as long as one constraint is not violated too badly.
25 From an implementation point of view this means that we can’t throw active nodes away when they get removed from theactive list as their info may still be necessary in this step.

28

C OMPUTATIONAL I NTELLIGENCE

A different approach would be to limit the search space by requiring that Q is lower thana certain constant, but from a user interface perspective it is much harder to understand thesignificance of the cutoff point if it is a combination of several constraints is used to generate
its value.
Technically though the two ways are identical as it is always possible to provide adefinition for f that results in the behavior as implemented, so it is more a matter of userinterface style than anything else.
If the column heights vary throughout the document, then the complexity of the basealgorithm is of order O(m2 ) where m is the total number of blocks xi in the document. If thealgorithm would calculate all coli, j then this would be m(m − 1)/2 computations, so this gives
us an upper bound. However, since many of them will be naturally infeasible, the numberof calculations actually needed to be carried out can be reduced a lot, making the problem
computable even for larger values of m.
The main loop has to be executed for each block and for xi = bi which can be assumed
to happen about half of the time and one needs to calculate cola,bi for all a ∈ A at this point.
Now the number of active nodes a with column(a) = k in that list is bounded by the first line
in equation (10) as active nodes get deactivated, once they are too far away from the current
breakpoint, i.e., more than Ck plus any available shrink in the material. So assuming thecolumn target height Ck is bounded (which it had better be in a real life scenario) as well as theability for material to shrink, then the maximum number of active nodes a with column(a) = k
will be smaller than c · n with c as a small constant and n the number of breakpoints possible
in material of height max(Ck ).
kHowever, due to the variation introduced by the ability of material to stretch and shrink
the active list will not contain just nodes related to a single column, but over time will growand contain nodes related to different columns. If we assume, for example, that there is±5% flexibility generally, then after looking at breakpoints for roughly 20 columns worth ofmaterial, we may find active nodes ending at column 19 (material was always stretched) or 21(material was always compressed) beside those for column 20 which would be the naturallength. Thus, with m growing the length of the active node list A will grow proportionallyto it and even though that factor of growth would be very small it will give us a complexity
bound of O(m2 ).
But there is a very common subclass of layouts in which the situation is much better: If
the target column heights Ck are equal for all columns or all columns after a certain index
and if the cost function Q only depends on general characteristics such as a common column
size,26 then it is possible to collapse different feasible solutions for a given breakpoint to oneeven if they are for different columns. This will reduce the search space that the algorithm
has to walk through considerably, and the complexity will be reduced to O(m) as now the
maximum length of the active list is bounded by a constant.
4.4. Double spread support
Providing support for shortening or lengthening the columns of a double spread meansthat if the active node a represents a column break for the last column k on a double spread,then the calculation of Qk+1
a,b in the main loop needs to be done 3 times with different values
for the height of column k + 1, namely Ck+1 and Ck+1 ± variation and we can only deactivate
a once Q is ∞ for all different column heights. Furthermore, for column k + 1 we now need to
26 This is the case for Q in the base algorithm as it only takes C as column related input. In the double spread extension thekvariant height Va and implicitly the column type Ta (which is a function of k) are additional inputs to Q and so individual active
nodes need to be maintained for any combination of their values. Here collapsing could happen for all columns that share thesame type and the same height variation value.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

29

F IGURE 9. Double spread support (Phase 3)
generate a new active node for each combination of k + 1,Ck+1 + variation for which there
exists a feasible candidate.
On the other hand, if such a new active node a0 has been created for column k + 1, thenwhatever height has been used for column k + 1 needs to be reused when evaluating Qk+2
a0 ,b0 for0some breakpoint b . And the same happens for all further columns of that spread. Thus thetarget height as input to f is no longer just depending on the current column but also on thesituation on previous column(s). It can be varied if we are starting a new spread or it needs tobe whatever the previous column was if we are on any other column of the spread.
To support this efficiently, we extend the active node data structure to keep track of thetype of column Ta that will start at a (i.e., a function of k) and the amount of height adjustment
Va that should be used on that column.27 Then, at the point in the algorithm where we are
generating new active nodes from feasible candidates (see Figure 9) we check the type ofcolumn that has started by the current active node a and ended at the current breakpoint asfollows:• If Ta = last, then the next column has flexibility and can be run a line long or short. We
model this by generating at this point not one but three new active nodes that are identical
except for the variation amount Va to be used on the next column: This is set to 0, or±baselineskip, respectively.
• If on the other hand Ta 6= last, then the variation amount is predetermined by the value
specified in the active node a that was used in the feasible candidate. For each group offeasible candidates (with the same value of k and Va ) we therefore generate a single newactive node a0 and set Va0 = Va .
It is important to reiterate that the above means that partitioning of the feasible candidates
in groups is not just based on the values for column k but on k and Va (the latter only if
27 Think of T as recording “column x out of y” so that each column is identifiable and we can test if we are in the last columnaof a spread.

30

C OMPUTATIONAL I NTELLIGENCE

Ta 6= last) and that for each such group one needs to generate a new active node (or a set of
active nodes).
In case Ci is constant partitioning needs to happen only on Ta and Va which reduces thecomplexity but still means that, compared to the base algorithm, a noticeable number of extra
active nodes need to be generated and processed.
The only other modification that is still needed, is to extend the definition of the costfunction Q from equation (10), as it now needs to incorporate the value of Va :(−∞if Hcoli, j − Scol
> Ck +Va
a
i, j
Qk,V
=
(13)
−
+
i, j
f (Ck , Hcoli, j , Scoli, j , Scoli, j , Pb j ,Va ) otherwise
The check whether or not the material fits the column is adjusted to include the heightvariation and the function f is extended to accept Va as input, so that deviations from the norm
(Va 6= 0) can be appropriately penalized by adding to the value returned by Q. By default, theframework uses the following definition for f :δ+ cspread variation for Va 6= 0+−
f (Ck , Hcoli, j , Scoli, j , Scoli, j , Pb j ,Va ) = k+VaδkotherwiseThis way, if a column is run long or short the constant cspread variation is added to the demerits,
thus by changing the value for this constant one can make it more or less likely that the heightof double spreads get changed by the algorithm.
4.5. Variation support
Support for variants in galley material (e.g., paragraphs with different line breaks resulting
in different number of lines, or in a different distribution hyphenation points) is handled byintroducing new types of control elements ci in the input stream that signal “start”, “switch”
and “end” of a variation set. Start and switch controls have an associated penalty Pci that isused to penalize the choice of that particular variation.
One difficulty introduced by variations is that they provide different amounts of material
along their variation paths. Thus the distance from the start of the document to any breakpoint
b after the variation block is no longer a single well-defined value. Instead it depends on
the route through which b has been reached. By supporting multi-path variations as wellas variations within variations this can get arbitrarily complicated. In the algorithm this is
resolved by manipulating the data stored in active nodes essentially by pretending that the
document has started on an earlier or later point. This way it becomes transparent for the
calculation of cola,b through which variation paths b has been reached.
The paths from all variation sets are uniquely labeled, so that every possible way to movefrom the start to the end of the document can be uniquely described by simply concatenating
the path labels.28
The active node data structure is extended to record in path(a) the cumulated path throughall variations up to the break point associated with a.
For variation support the main loop of the base algorithm is then extended as outlined in
Figure 10 by managing the following additional cases:
Case xi = ci with type(ci ) = start This signals the start of a variation set. We make a copy
+ , S̄− fromof the active node list Asaved ← A and we also file away the totals H̄start , S̄start
start
28 The precise method is of no importance, as long as it is possible to exactly reconstruct the selection made to achieve thebest solution. In the prototype implementation sequential numbers for both the variation sets and the individual paths withinthem have been used. For example, 1-2;2-2;3-1 means that the second path was taken in in the first and second variation
set, while the first path was taken in the third variation set.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

31

F IGURE 10. Handle paragraph variation data (Phase 3)
the beginning of the document to the current position for later use. A label L for the current
variation path is chosen and P = Pci is saved as the penalty to add to the demerits in casethis path is chosen.29 Then we proceed with the next block xi+1 .
Case xi = ci with type(ci ) = switch In this case we reached the end of a variation path. All
nodes currently in the active node list A are either on the current variation path (because
they have been only recently created) or they are from before the variation block, but wehave evaluated the breakpoints on the variation path against them.
So we update all a ∈ A by appending the label for the finished variation to the path in eacha, i.e., path(a) ← path(a);L and add P to demerits(a).
If this is the first variation in the variation block we save the totals from the beginning of+ , S̄− for later use.
the document to the current point in H̄first , S̄first
first
Otherwise we also update the totals stored in all a ∈ A with the height difference between
the current and the first variation path, i.e., H̄first − H̄ci , etc. This way later on Hcola,b for
29 The penalty P has been calculated in Phase 2 from the difference in quality between the optimal paragraph-breaking andci
the paragraph-breaking with a non-zero looseness value (TEX returns a numerical value for the line-breaking quality). Thisdifference is then multiplied with the user-constraint cpara variation to obtain that penalty.

32

C OMPUTATIONAL I NTELLIGENCE

some breakpoint b after the variation block can still be simply calculated by subtracting thetotals at b from the totals at a, i.e., the calculation is transparent to the path by which b wasreached.
Finally we save away the updated active node list A. We then restore the context we were in+ and S̄− as the current
before the first variation, i.e., A ← Asaved and we restore H̄start , S̄start
start
totals. We then select a new label L and set P ← Pci for the next variation path. Then we
proceed to xi+1 .
Case xi = ci with type(ci ) = finish The end of the variation block has been reached. We
update the active node list as described in the switch case and then combine it with theactive node lists saved earlier. This will then form the complete new active node list going
forward.
All that remains to do otherwise, is to restore the totals to the values at the end of the firstvariation (as the active nodes in all other variations have been adjusted to pretend this is+ , S̄− .
correct). These values have been previously recorded as H̄first , S̄first
firstStarting from the final active node a when finishing the algorithm, we arrive at the optimal
solution for the whole document by determining the list of active breaks that lead to this nodeand examining all selected variation paths as recorded in path(a). The latter is an integral partof the solution as many variation blocks will end up between two chosen breakpoints, yet it isimportant to know which path was used in the construction since we have to replicate thatdecision in the typesetting phase (Phase 4).

4.6. Complexity of the extensions
It is easy to see that both extensions do not change the overall complexity of the algorithm,
i.e., it stays O(m2 ) in the general case and O(m) if the column height is constant after a certain
point.
In the double spread case the maximum length of the active list will have an additional
factor of 3 × number of spread columns due to the variability when starting a new spread andthe fact that we need to distinguish active nodes for different columns on a spread.
The situation with variation blocks is worse, as the number of active nodes depends on
the number of paths through the variation sets seen along the way. The number of different
paths through variations v1 , . . . , v` is ∏`i=1 wi with wi being the number of “ways” throughvariation set vi . Thus this is exponentially growing in `, but fortunately ` is bounded by the
number of breakpoints that can fit on a single column. Therefore this product is actually alsoof complexity O(1) though unfortunately with a much larger constant if we have columns
with many variable paragraphs; see Section 4.7.
In case of constant column heights Ci , the overall complexity is O(m) for the basealgorithm, because it is possible to collapse all active nodes associated with breakpoint b into
one, regardless of the column they did end. This limits the maximum length of the active node
list so that it becomes a constant in the complexity calculation. This argument also holds true
for the variation set extension (with the small practical problem that the actual constant isfairly large).
In case of the double spread extension we have dependencies between different columns,
therefore a solution for column one is not necessarily a solution for all other columns.
Nevertheless, collapsing is also possible with the only difference, that we have to keep thebest feasible candidate for each combination of Ta and Va in the running. Again this makes
the length of the active node list independent from m so that the overall complexity of thealgorithm drops to O(m).

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

33

4.7. Computational experience
To gain experience with the behavior of the algorithm and its extensions it was tested on
different types of novels. A few of these documents and the respective findings are listed inTable 1. They differ in size, average paragraph length, frequency of headings, complexity andother aspects and are a good representation of the complete set of documents tested. These
documents are “Alice’s Adventures in Wonderland” by Lewis Carroll, “Call of the Wild” byJack London, “Fairy Tales” by the brothers Grimm translated into English by Edgar Taylorand Marian Edwardes, “Pride and Prejudice” by Jane Austen and “The Old Curiosity Shop”
by Charles Dickens.
All documents have been set in two columns with a width of 8 cm. Each column could
hold 46 lines of text and the paragraph requirements have been fairly strict: No widows ororphans and only a small amount of flexibility (+1pt) for the paragraph separation. This meansthat in each column one could gain a flexibility of up to 2 lines (but only when there are 8 ormore paragraphs in the column and we accept a stretch of up to 3 times the nominal value
which corresponds to a badness of 2700).
This type of paragraph flexibility (indicated by “flex” in the table) is rather uncommon
when typesetting novels, as there one usually tries to keep all text lines on a grid. But it
is often used with technical documentation that contains objects of sizes that differ from anormal text line height. It is therefore the default used by LATEX.
For comparison all trials have also been run without allowing for any flexible space
between paragraphs (this is indicated by “strict” in the table). Obviously this means that thepagination algorithm has (even) fewer options to choose from. Thus, with LATEX’s greedy
algorithm we see more “ugly” columns and with the optimizing algorithm we see additional
cases where the algorithm is unable to find any solution at all.
The first row for each document in the table gives the results when processing the
document using the standard LATEX pagination, i.e., a greedy algorithm and in all cases there
are a large number of bad column breaks that would require manual attention (between 4%(Carroll) and 16% (London) of all columns).
The second row for each document then shows the results from LATEX’s greedy algorithm
but without allowing any flexibility between paragraphs. In this case the number of issues
rises up to 40% of all columns (Carroll) and between 15% and 25% for all others.
The base algorithm (i.e., optimizing across the whole document but without adding any
additional flexibility through an extension) shows a maximum active list length of 37, 9(!),
22, 42 and 41 (flex) and 6, 2, 20, 2 and 2 (strict), respectively. As a column with 46 lines
would have at most that many breakpoints, these values are in line with expectations, i.e.,
the inherent galley flexibility contributes only a very small factor, so only with Austen andDickens we see a maximum close to 46. This is due to the fact that these documents are fairly
long (several hundred columns) and have relatively short paragraphs so that the paragraphflexibility accumulates and some breakpoints end up being candidates for ending different
columns. At the same time we see that the maximum drops sharply if the paragraph flexibility
is removed.
The very low flex value for London is due to the fact that this document has very longparagraphs (average of 4 per column) and thus is unable to build up any significant flexibility
that makes the active list grow towards its boundary.
It is therefore also not surprising that the base algorithm doesn’t find a solution (except
with Austen and Dickens when using flex), as the number of alternatives to consider are nothigh enough to resolve all obstacles resulting from widows and orphans.
When applying the spread extension the length of the active list gets bounded by 46 × 3 ×
4 = 552 so again the observed maxima of 432, 263, 485, 486 and 487 (flex) are in line withexpectations. Without flex the maxima are also higher than before but nowhere close to thehighest possible value. It may appear surprising that this additional flexibility does not result

34

C OMPUTATIONAL I NTELLIGENCETABLE 1.

Document performance using different algorithm extensions
document
columns blocks

Alice in Wonderland
greedy, strict
base, flex
base, strict+ spread, flex
+ spread, strict+ variations, flex
+ variations, strict+ variations, spread, flex
+ variations, spread, strict

72
72
–
–
–
–
74d
–
72
70d

Call of the Wild
greedy, strict
base, flex
base, strict+ spread, flex
+ spread, strict+ variations, flex
+ variations, strict+ variations, spread, flex
+ variations, spread, strict

78
78
–
9148
–
9148
78
9148
79d 9148
78 14970
78 14970
78 14970
78 14970

Grimm’s Fairy Tales
greedy, strict
base, flex
base, strict+ spread, flex
+ spread, strict+ variations, flex
+ variations, strict+ variations, spread, flex
+ variations, spread, strict

236
236– 27907– 27907234d 27907– 27907239d 59110
236 59110
236 59110
237d 59110

Pride and Prejudice
greedy, strict
base, flex
base, strict+ spread, flex
+ spread, strict+ variations, flex
+ variations, strict+ variations, spread, flex
+ variations, spread, strict

315
315
316d 34645– 34645
312d 34645– 34645315d 56861
314d 56861
314d 56861
314d 56861

The Old Curiosity Shop
greedy, strict
base, flex
base, strict+ spread, flex
+ spread, strict+ variations, flex
+ variations, strict+ variations, spread, flex
+ variations, spread, strict

554
554
555d 60480– 60480556d 60480– 60480558d 91547
556d 91547
560d 91547
555d 91547

active list
max averageparagraphs
total variableavailable loosenessa-1/0 -1/1 -1/2 0/1 0/2

833
6943
6943
6943
6943
9473
9473
9473
9473

37
6
432
10
602
261
7076
1566

12
1
122
2
55
19
496
169

111

6

15

0 89 1

340
9
2
263
41
263
263
3156
3156

2
1
134
14
68
63
704
637

139

11

3

0 124 1

1041
22
4
20
1
485 319
146
12
437
92
422
86
5532 1030
4980 968

441

10 50 21 318 42

2127
42
2
486
25
633
633
7596
7596

14
1
347
4
73
59
837
766

483

10 51

6 397 19

4097
41
2
487
22
1084
676
10932
8832

24
1
359
3
74
63
851
799

a A count of paragraphs that can be affected by setting specificlooseness values. For example, the column of -1/2 counts all
paragraphs that could be shortened by one line and extended
by up to two lines.
b Badness of columns: “Good” means the column material isstretched within the specified limits (b < 2000); “bad” meansa noticeable stretch (2000 6 b < 4000) and “ugly” meansthat the space in the column is stretched more than 3.4 times

768

65 33

2 653 15

vertical badnessb
good bad ugly

run
time

69 0 2+1
40 4 1+27
no solutionc
no solutionc
no solutionc
no solutionc
73 1–
no solutionc
71 1
–
70 –
–

< 1s

64 1 9+4
62 0 0+16
no solutionc
no solutionc
78 –
–
79 –
–
78 –
–
78 –
–
78 –
–
78 –
–

< 1s

212 6 6+12
198 1 0+37
no solutionc
no solutionc
234 ––no solutionc
239 –
–
236 –
–
236 –
–
237 –
–

< 2s

291 8 7+9229 14 0+73
316 ––no solutionc
312 ––no solutionc
315 –
–
314 –
–
314 –
–
314 –
–

< 2s

524 12 9+9
421 12 0+121
555 ––no solutionc
556 ––no solutionc
558 –
–
556 –
–
560 –
–
555 –
–

< 3s

≈ 6s
≈ 10s
≈ 5s

≈ 4s
≈ 4s
≈ 6s
≈ 5s
≈ 12s
≈ 11s

≈ 14s
≈ 15s
≈ 14s
≈ 67s
≈ 55s

≈ 10s
≈ 17s
≈ 16s
≈ 14s
≈ 58s
≈ 45s

≈ 17s
≈ 32s
≈ 25s
≈ 22s
≈ 116s≈ 100sits available flexibility (4000 6 b) or is infinitely bad in TEX’seyes (b = 10000) indicated by the second value.
c The pagination algorithm ran out of options (active list
empty) and produced one or more overfull columns as an
emergency fix.
d The optimized solution has a different number of columns
compared to the default LATEX solution.

A G ENERAL L UATEX F RAMEWORK FOR G LOBALLY O PTIMIZED PAGINATION

35

in a solution for Carroll, but this is due to the fact that this document contains an unbreakableobject of nearly the height of a column, so that it requires a much higher amount of flexibility
to move this out of a break position. Figure 1 on page 4 shows these problematic pages.
As discussed in Section 4.6, the factor by which the active node list can increase in case ofparagraph variations is basically the product ∏`i=1 wi where the wi is the number of different
ways one can get through the variation set vi and ` is the number of variation sets in thecurrent column. The majority of the variation sets in the texts by Carroll and London havew = 2 and only a few 3. Grimm and Austen on the other hand have 113 and 76 variation setswith w = 3 or 4, respectively. However, Carroll’s paragraphs are much shorter on average,
thus more fit on a page and larger values for ` are likely. So seeing a factor of 16, 30, 20, 16
and 26, respectively, for the five documents again fits with expectations.
With the double spread extension we vary the column height by one line and given 46
lines per column introduce an additional flexibility of roughly ±2.2%. The important aspectis that in contrast to variation sets this flexibility will be available on all columns and thus thechange in the active node list length should be fairly uniform across all documents. In contrast
the paragraph variation extension will only make a noticeable difference in that length whenseveral variable paragraphs are close together. Again we can observe this difference: withthe spread extension the average and the maximum are fairly close to each other, while theaverage length when applying paragraph variations is noticeably smaller.
When running the algorithm in its current prototype implementation with both extensions
applied we can see a time increase of a factor of 15 to 100 compared to a run using standard
LATEX. While this sounds large, we have to realize that, this means less than a second per pagefor a globally optimized document. When the author started to work with TEX, processing
time for a single page was often 30 seconds and more. Thus, global optimization, even withadditional bells and whistles added, has become a workable option.
5. CONCLUSION AND FURTHER WORKThe main contribution of this paper is the definition and implementation of a generalframework for experimenting with globally optimized pagination algorithms. This framework
will enable researchers to quickly test out new strategies for pagination and make themavailable to a larger audience with ease.30
All constraints are parameterized so that experimenting with different value combinations
is a simple matter of adjusting the values in a configuration file. More complex adjustments,
such as supplying different objective functions or a different method to calculate the column
badness, can be done by replacing a Lua-function with new code. As Lua is an interpreted
language that code can be loaded at runtime, i.e., as part of the configuration as well.
Experiments with a base algorithm for globally optimized pagination have shown that therelative performance hit, compared to a greedy algorithm, is neglectable with today’s powerfulcomputer systems (i.e., processing time increases by a factor of < 8 which means 10 insteadof 1.3 seconds for a document such as Austen). However, with many documents (that do notcontain enough flexible vertical space) the algorithm will run out of alternatives to optimize
and thus manual correction, just as with the greedy algorithm, will still be necessary.31
For successful global optimization it is therefore important to develop methods that
add additional flexibility to the pagination process. In this paper we introduced two suchmethods: The approach of running columns on double spreads one line short or long and
30 The framework will eventually become part of the standard T X distributions.

E

31 There is still a huge advantage: The number of issues will be noticeably smaller and resolving them normally doesn’t

require an iterative process, which is the case with the greedy algorithm.

36Computational Intelligence

the use of variants in the text. The latter was implemented by automatically providing all
paragraph variants (i.e., paragraphs formatted with different numbers of lines), wheneverthis can be done without compromising the quality on the micro-typography level beyond a
specified tolerance.
When applying the algorithm with the extensions we add enough additional flexibility to
fully optimize (nearly) every document without any manual intervention.32 And the price to
pay is acceptable if it avoids hours of iterative tinkering that are otherwise necessary whenmanually optimizing the results of a greedy algorithm. And in fact, what is typically been
done to manually resolve such issues is precisely what the extensions will automaticallyintegrate into the algorithm: redoing some paragraphs to make them longer or shorter andrunning some columns long or short combined with placing explicit breaks in strategic places.
The base algorithm outlined in this paper does not handle additional auxiliary input
streams such as floats (which of course raises the complexity further). As there are quite
different models possible (some of them touched upon in Section 1.4), such work should be
provided as extensions to the base algorithm, to enable easy comparison between different
approaches. Results from such types of extensions are presented in Mittelbach (2017).
Other interesting research topics are alternative approaches for limiting the search spacein meaningful ways, or strategies that only locally consider variants if the pagination runs outof good options.
The current algorithm assumes that columns have a defined size (which can vary fromcolumn to column but is otherwise fixed) and that these columns are filled sequentially. Thismeans that filling strategies that balance material across columns are not supported and cannot
be optimized by the algorithm. It would therefore be interesting and important to develop
alternative or extended algorithms that support these important types of designs as well.
REFERENCES
Brüggemann-Klein, Anne, Rolf Klein, and Stefan Wohlfeil. 2003. Computer science inperspective. Springer-Verlag New York, Inc., pp. 49–68. New York, NY, USA. ISBN 3-540-00579-X.
http://dl.acm.org/citation.cfm?id=865449.865455.
Ciancarini, Paolo, Angelo Di Iorio, Luca Furini, and Fabio Vitali. 2012. High-quality
pagination for publishing. Software—Practice and Experience, 42(6):733–751. ISSN 0038-0644 (print),
1097-024X (electronic). http://dx.doi.org/10.1002/spe.1096.
Enlund, Nils E. S. 1991. Electronic Full-Page Make-Up of Newspaper in Perspective, pp. 318–323.
Mainz, Germany: Gutenberg-Gesellschaft, Internationale Vereinigung für Geschichte und Gegenwart der
Druckkunst e.V.
Gange, Graeme, Kim Marriott, and Peter Stuckey. 2012. Optimal guillotine layout.
In Proceedings of the 2012 ACM Symposium on Document Engineering, DocEng ’12, ACM, New York,NY, USA. ISBN 978-1-4503-1116-8. pp. 13–22. 10.1145/2361354.2361359. http://doi.acm.org/
10.1145/2361354.2361359.
Goossens, Michel. 2010. The XETEX Companion: TEX meets OpenType and Unicode. Switzerland.
http://xml.web.cern.ch/XML/lgc2/xetexmain.pdf.
Hailpern, Joshua, Niranjan Damera Venkata, and Marina Danilevsky. 2014. Pagination: It’s what you say, not how long it takes to say it. In Proceedings of the 2014 ACM Symposium on
Document Engineering, DocEng ’14, ACM, New York, NY, USA. ISBN 978-1-4503-2949-1. pp. 147–156.
10.1145/2644866.2644867. http://doi.acm.org/10.1145/2644866.2644867.
Hàn Th´ê Thành. 2000. Micro-typographic extensions to the TEX typesetting system. Ph.D. dissertation,
Faculty of Informatics, Masaryk University, Brno, Czech Republic.
Harrower, Tim. 1991. The Newspaper Designer’s Handbook. Wm. C. Brown Publishers, Dubuque.

32 It is certainly possible to construct documents that cannot be optimized even then. But for most documents even using justone of the extensions will be sufficient.

A General LuaTEX Framework for Globally Optimized Pagination

37

Hassan, Tamir, and Andrew Hunter. 2015. Knuth-plass revisited: Flexible line-breaking for automatic
document layout. In Proceedings of the 2015 ACM Symposium on Document Engineering, DocEng’15, ACM, New York, NY, USA. ISBN 978-1-4503-3307-8. pp. 17–20. 10.1145/2682571.2797091.
http://doi.acm.org/10.1145/2682571.2797091.
Holkner, A. 2006. Global multiple objective line breaking. Master’s thesis, School of Computer Scienceand Information Technology, RMIT University, Melbourne, Victoria, Australia.
Hurlburt, Allen. 1978. The grid: A modular system for the design and production of newspapers,
magazines, and books. Van Nostrand Reinhold, New York.
Jacobs, Charles, Wilmot Li, and David H. Salesin. 2003. Adaptive document layout via manifold
content. In Second International Workshop on Web Document Analysis (wda2003), Liverpool, UK, 2003.
Jacobs, Charles, Wilmot Li, Evan Schrier, David Bargeron, and David Salesin. 2003.
Adaptive grid-based document layout. Association for Computing Machinery, Inc. http://research.
microsoft.com/apps/pubs/default.aspx?id=69470.
Kido, Yusuke, Hikaru Yokono, Goran Topić, and Akiko Aizawa. 2015. Document layout
optimization with automated paraphrasing. In Proceedings of the 2015 ACM Symposium on Document
Engineering, DocEng ’15, ACM, New York, NY, USA. ISBN 978-1-4503-3307-8. pp. 13–16. 10.1145/
2682571.2797095. http://doi.acm.org/10.1145/2682571.2797095.
Knuth, Donald E. 1986a. The TEXbook, Volume A of Computers and Typesetting. Addison-Wesley,
Reading, MA, USA. ISBN 0-201-13447-0.
Knuth, Donald E. 1986b. TEX: The Program, Volume B of Computers and Typesetting. Addison-Wesley,
Reading, MA, USA. ISBN 0-201-13437-3.
Knuth, Donald E., and Michael F. Plass. 1981. Breaking Paragraphs into Lines. Software—
Practice and Experience, 11(11):1119–1184.
LuaTEX development team. 2017. LuaTEX Reference Manual, Version 1.0.4. http://www.
luatex.org/svn/trunk/manual/luatex.pdf.
Mittelbach, Frank. 1990. E-TEX: Guidelines for future TEX extensions. TUGboat, 11(3):337–345. ISSN
0896-3207.
Mittelbach, Frank. 2013. E-TEX: Guidelines for future TEX extensions — revisited. TUGboat, 34(1):47–
63. ISSN 0896-3207.
Mittelbach, Frank. 2016. A general framework for globally optimized pagination. In Proceedings of the2016 ACM Symposium on Document Engineering, DocEng ’16, ACM, New York, NY, USA. ISBN 978-14503-4438-8. pp. 11–20. 10.1145/2960811.2960820. http://doi.acm.org/10.1145/2960811.
2960820.
Mittelbach, Frank. 2017. Effective floating strategies. In Proceedings of the 2017 ACM Symposium on
Document Engineering, DocEng ’17, ACM, New York, NY, USA. ISBN 978-1-4503-4689-4. pp. 29–38.
10.1145/3103010.3103015. http://doi.acm.org/10.1145/3103010.3103015.
Mittelbach, Frank, and Chris Rowley. 1992. The pursuit of quality: How can automated typesetting
achieve the highest standards of craft typography? In EP92—Proceedings of Electronic Publishing, ’92,
International Conference on Electronic Publishing, Document Manipulation, and Typography, Swiss Federal
Institute of Technology, Lausanne, Switzerland, April 7-10, 1992. Edited by C. Vanoirbeek and G. Coray.
Cambridge University Press, New York. ISBN 0-521-43277-4. pp. 261–273.
Piccoli, Ricardo, João Oliveira, and Isabel Manssour. 2012. Optimal pagination and content
mapping for customized magazines. Journal of the Brazilian Computer Society, 18(4):331–349. ISSN
1678-4804. 10.1007/s13173-012-0066-6. https://doi.org/10.1007/s13173-012-0066-6.
Plass, Michael Frederick. 1981. Optimal Pagination Techniques for Automatic Typesetting Systems.
Ph. D. thesis, Stanford University, Department of Computer Science, Stanford, California 94305. Report No.
STAN-CS-81-970.
Wohlfeil, Stefan. 1998. On the Pagination of Complex Book-Like Documents. Ph. D. thesis,
Fernuniversität Hagen, Hagen, Germany.