Sample PDF Document

Robert Maron
Grzegorz Grudziński

February 20, 1999

2
Contents

1 Template 5
1.1 How to compile a .tex file to a .pdf file . . . . . . . . . . . . . 5
1.1.1 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 How to use the tools . . . . . . . . . . . . . . . . . . . . 5
1.2 How to write a document . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 The main document . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Chapters . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Spell-checking . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 LATEX and pdfLATEX capabilities . . . . . . . . . . . . . . . . . . . 7
1.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 LATEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.3 pdfLATEX . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3
4 CONTENTS
Chapter 1

Template

1.1 How to compile a .tex file to a .pdf file

1.1.1 Tools
To process the files you (may) need:

• pdflatex (for example from tetex package ≥ 0.9-6, which you can
get from Red Hat 5.2);

• acroread (a PDF viewer, available from [Link]

• ghostscript ≥ 5.10 (for example from Red Hat Contrib) and ghostview
or gv (from RedHat Linux);

• efax package could be useful, if you plan to fax documents.

1.1.2 How to use the tools

Follow these steps:

1. put all source .tex files in one directory, then chdir to the directory (or put
some of them in the LATEXsearch path — if you know how to do this);

2. run “pdflatex [Link]” on the main file of the document three times
(three — to prepare valid table of contents);

3. to see or print the result use acroread (unfortunately some versions of

acroread may produce PostScript which is too complex), or

5
6 CHAPTER 1. TEMPLATE

4. run ghostscript: “gv [Link]” to display or:

“gs -dNOPAUSE -sDEVICE=pswrite -q -dBATCH -sOutputFile=[Link] [Link]”
to produce a PostScript file;

5. run “fax send phone-number [Link]” as root to send a fax, or — if you

know how to do this — modify the fax script to be able to fax .pdf files directly
(you have to insert “|%PDF*” somewhere. . . ).

1.2 How to write a document

1.2.1 The main document
Choose the name of the document, say document. Copy [Link] to
[Link], then edit it, change the title, the authors and set proper in-
clude(s) for all the chapters.

1.2.2 Chapters
Each chapter should be included in the main document as a separate file. You can
choose any name for the file, but we suggest adding a suffix to the name of the
main file. For our example we use the file name document_chapter1.tex.
First, copy template_chapter.tex to document_chapter1.tex
and add the line

\include{document_chapter1}

in the [Link], then edit document_chapter1.tex, change the

chapter title and edit the body of the chapter appropriately.

1.2.3 Spell-checking
Do use a spell-checker, please!
You may also want to check grammar, style and so on. Actually you should
do it (if you have enough spare time). But you must check spelling!
You can use the ispell package for this, from within emacs, or from the
command line:

ispell -t document_chapter1.tex
1.3. LATEX AND PDFLATEX CAPABILITIES 7

1.3 LATEX and pdfLATEX capabilities

1.3.1 Overview
First you edit your source .tex file. In LATEX you compile it using the latex
command to a .dvi file (which stands for device-independent). The .dvi file
can be converted to any device-dependent format you like using an appropriate
driver, for example dvips.
When producing .pdf files you should use pdflatex, which produces di-
rectly .pdf files out of .tex sources. Note that in the .tex file you may need
to use some PDF specific packages.
For viewing .tex files use your favourite text editor, for viewing .dvi files
under X Window System use xdvi command, .ps files can be viewed with gv
(or ghostview) and .pdf files with acroread, gv or xpdf.

1.3.2 LATEX
A lot of examples can be found in this document.
You should also print
• doc/latex/general/[Link] and
• doc/latex/general/[Link]
from your tetex distribution (usually in
• /usr/share/texmf or
• /usr/lib/texmf/texmf).

1.3.3 pdfLATEX
Consult doc/pdftex/[Link] from your tetex distribution for more
details. Very useful informations can be found in the hyperref and graphics
package manuals:
• doc/latex/hyperref/[Link] and
• doc/latex/graphics/[Link].

1.3.4 Examples
References
MIMUW
8 CHAPTER 1. TEMPLATE

Hyperlinks
This is a target.
And this is a link.

Dashes, etc.
There are three kinds of horizontal dash:

• - (use inside words; for example “home-page”, “X-rated”)

• – (use this one between numbers; for example “pages 2–22”)

• — (use this one as a sentence separator — like here)

National characters
• ó, é, í, . . .

• è, à, ì, . . .

• ô, ê, . . .

• õ, ñ, . . .

• ö, ë, . . .

• ż

• a,˛ e˛

• ł, ø, ß

There are other ways to do this, see the documentation for inputenc pack-
age.

Reserved characters
Some characters have some special meaning, thus cannot be entered in the usual
way.

• $&%#_{}

• \

• ˜ˆ
1.3. LATEX AND PDFLATEX CAPABILITIES 9

Math
• 12 , 12n , . . .

• i1 , i2n , . . .
1 2n
• ,
2 2−3
, ...

• α, β, γ, Ω, . . .

• →, ⇒, ≥, 6=, ∈, ?, . . .
√
• 2, . . .

• 2 + 2, . . .

For more examples and symbols see chapter 3 of [Link].

Fonts
• Roman

• Emphasis

• Medium weight — the default

• Boldface

• Upright

• Slanted

• Sans serif

• S MALL CAPS

• Typewriter

• and sizes:

– tiny

– scriptsize

– footnotesize
– small
– normalsize
10 CHAPTER 1. TEMPLATE

– large
– Large
– LARGE
– huge
– Huge
Contents

1 Roots of Geometry and Topology . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Platonic Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Euler Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Disk Packings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Sphere Packings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Space Filling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Part I Tessellations

2 Voronoi and Delaunay Diagrams. . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1 Convex Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Delaunay Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Maximally Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.6 Incremental Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.7 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Weighted Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1 Apollonius Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Power Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Weighted Delaunay Triangulations . . . . . . . . . . . . . . . . . . . . 20
3.4 Geometric Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Three Dimensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Cube Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3 BCC Lattice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4 FCC Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5 Quadratic Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

vii
viii Contents

Part II Complexes

5 Alpha Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1 Jarvis’ Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 The Alpha Shape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3 Union of Disks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.4 Voronoi Decomposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.5 Filtration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.6 Space-Filling Models of Proteins . . . . . . . . . . . . . . . . . . . . . 38
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6 Holes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.1 Holes in the Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.2 Filtration by Thickening . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3 Pockets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.4 Iterative Stochastic Construction. . . . . . . . . . . . . . . . . . . . . . 44
6.5 Hierarchical Pocket Structure . . . . . . . . . . . . . . . . . . . . . . . . 44
6.6 Tunnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7 Area Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7.1 Space-Filling Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7.2 Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . 48
7.3 Independent Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.4 Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7.5 Full Subcomplexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Part III Homology

8 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8.1 Topology and Topology Equivalence . . . . . . . . . . . . . . . . . . 57
8.2 2-Manifolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
8.3 Classification of Compact Surfaces. . . . . . . . . . . . . . . . . . . . 59
8.4 Simplicial Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
8.5 Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

9 Homology Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.1 Little Creatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.2 Chain Groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
9.3 Chain Complex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
9.4 Cycles and Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
9.5 Homology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Contents ix

9.6 Euler-Poincaré Formula. . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

9.7 Some Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

10 Complex Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
10.1 Abstract Simplicial Complexes. . . . . . . . . . . . . . . . . . . . . . . 73
10.2 Homotopy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
10.3 Homotopy Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10.4 Nerves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10.5 Čech Complexes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.6 Vietoris-Rips Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Part IV Persistence

11 Filtrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
11.1 Alpha Complex Filtration . . . . . . . . . . . . . . . . . . . . . . . . . . 83
11.2 Incremental Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
11.3 Topological Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
11.4 Birth and Death . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
11.5 Barcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
11.6 Persistence Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

12 PL Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
12.1 Piecewise Linear Interpolation . . . . . . . . . . . . . . . . . . . . . . . 91
12.2 Sublevel Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
12.3 Full Subcomplexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
12.4 PL 2-Manifolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
12.5 Alternating Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
12.6 Bottleneck Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
12.7 Stability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

13 Matrix Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
13.1 Boundary Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
13.2 Reduction Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
13.3 Translation to Barcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
13.4 Uniqueness of Pivots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
13.5 Alternative Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
[Link]