Triangulations: Structures for Algorithms and Applications

Preface......Page 4
Triangulations in Mathematics......Page 14
Combinatorics and triangulations......Page 15
Optimization and triangulations......Page 26
Algebra and triangulations......Page 34
The rest of this book......Page 47
Exercises......Page 50
Polyhedra and cones......Page 54
Point configurations......Page 58
Geometry of point configurations......Page 61
A closer look at the definition of triangulation......Page 64
There is always a triangulation......Page 65
A famous example: the Delaunay triangulation......Page 67
Regular subdivisions and their structure......Page 70
Polyhedral subdivisions......Page 73
Regular subdivisions, again......Page 78
Corank-one configurations and circuits......Page 83
Almost-triangulations and flips......Page 85
Vector configurations and their triangulations......Page 87
Vector configurations......Page 88
Polyhedral subdivisions of vector configurations......Page 90
Regular subdivisions of vector configurations......Page 92
Simplicial complexes......Page 94
The f-vector of a simplicial complexes......Page 95
Linear constraints on the f-vector......Page 98
Exercises......Page 101
Some basic properties......Page 104
A few examples of triangulations in the plane......Page 106
Placing and pulling triangulations......Page 107
Delaunay triangulations......Page 108
Greedy and minimum weight triangulations......Page 113
The set of all triangulations of a point set......Page 118
The exact number of triangulations......Page 119
The maximum possible number of triangulations......Page 123
The minimum possible number of triangulations......Page 126
The poset of subdivisions......Page 127
Flips in triangulations......Page 130
All triangulations of a point set in the plane are connected by flips......Page 131
Effective enumeration of triangulations......Page 134
Further properties of the graph of flips......Page 139
Pseudo-triangulations......Page 142
Life in three dimensions......Page 144
The number of tetrahedra......Page 145
Monotone flipping does not (always) work......Page 148
The number of flips......Page 152
Notes and References......Page 156
Exercises......Page 157
Combinatorics of configurations......Page 160
Dependences, circuits, and the intersection property......Page 161
Evaluations, cocircuits, and the union property......Page 166
Gale transforms and the duality between circuits and cocircuits......Page 171
Pyramids and joins......Page 176
Prisms and products......Page 178
Deletion......Page 180
Contraction......Page 182
One-point suspension......Page 186
The placing (or pushing) triangulation......Page 189
The pulling triangulation......Page 191
Lexicographic triangulations......Page 193
Pushing and pulling refinements......Page 194
Characterization of flips via circuits......Page 196
Flips via walls......Page 199
Geometric characterizations......Page 201
Combinatorial characterizations......Page 214
Exercises......Page 217
Regular Triangulations and Secondary Polytopes......Page 220
Motivating examples......Page 221
Statement of the main theorem......Page 225
Dimension and affine span of the secondary polytope......Page 228
Secondary cones......Page 232
The secondary fan......Page 236
Proof of the main theorem......Page 240
Edges of the secondary polytope......Page 244
Monotone paths on the secondary polytope......Page 247
Facets of the secondary polytope......Page 252
The chamber fan......Page 254
Flips in the chamber fan......Page 259
Configurations with d+3 points......Page 268
Configurations with d+4 points......Page 272
Lawrence polytopes, and the complexity of secondary polytopes......Page 275
Exercises......Page 281
Cyclic polytopes......Page 286
Warm-up example: two dimensions......Page 287
Combinatorial properties of cyclic polytopes......Page 288
Triangulations as sections of the canonical projection......Page 294
Higher Stasheff-Tamari posets......Page 296
The structure theorem for the first Stasheff-Tamari poset......Page 298
Cyclic polytopes have many triangulations......Page 301
Products of two simplices......Page 304
The prism over a simplex......Page 305
The product of simplices......Page 309
Staircase triangulations......Page 312
Non-regular triangulations of products of simplices......Page 315
Small 0/1 non-regular triangulations......Page 322
Two simple ways to triangulate any cube......Page 325
Triangulating high-dimensional cubes. State of the art......Page 327
Cubes of three dimensions......Page 330
Cubes of four dimensions......Page 332
Slices of cubes: triangulations of hypersimplices......Page 335
Birkhoff\'s polytope......Page 341
Exercises......Page 345
Some Interesting Triangulations......Page 348
A theme with many variations......Page 349
Twelve proofs of non-regularity......Page 353
Dimension 3: A zig-zag grid......Page 356
Locally acyclic orientations and triangulations of products......Page 360
L. a. o.\'s without reversible edges......Page 363
Dimension 4: Layers of prisms......Page 367
Locally acyclic orientations of boundary subcomplexes......Page 369
Unimodular triangulations in different components of the graph of triangulations......Page 371
Exponential number of components in the graph of flips......Page 372
Dimension 6: A disconnected graph of triangulations in general position......Page 373
The building block: Gale octagons......Page 374
Dimension 6: seventeen points in special position......Page 376
A disconnected space of triangulations in general position......Page 380
Exercises......Page 385
Chirotopes......Page 388
Computing the chirotope......Page 389
Computing circuit and cocircuit signatures from the chirotope......Page 394
Verification and realizability......Page 396
Constructing regular triangulations in practice......Page 397
Checking regularity of a triangulation......Page 398
Listing and enumerating triangulations......Page 399
Exploring a flip-graph component......Page 400
Enumeration of all triangulations......Page 401
Enumeration with symmetry......Page 403
Implementation issues......Page 404
Bounding the number of triangulations......Page 406
Optimization......Page 409
A linear optimization approach: the universal polytope......Page 411
Relaxations of the universal polytope and its edges......Page 417
Equidecomposable and weakly neighborly polytopes......Page 421
A very quick review of complexity classes......Page 424
The hardness of the planar constrained triangulation problem......Page 426
Hardness of minimum length triangulations in the plane......Page 433
Hardness of minimal size triangulations of convex polytopes......Page 435
Exercises......Page 439
Monotone paths......Page 444
Zonotopal tilings......Page 447
Compatible subdivisions and the fiber polytope......Page 449
An example......Page 456
Mixed subdivisions and the Minkowski projection......Page 458
Subdivisions in the Cayley embedding and the Cayley projection......Page 463
The Cayley trick......Page 465
Product of a triangle and k-simplex......Page 470
Lattice polytopes and unimodular triangulations......Page 474
Triangulations of lattice polygons......Page 476
Existence of unimodular triangulations......Page 480
Ehrhart polynomials and unimodular triangulations......Page 486
Triangulations and Gröbner bases......Page 489
Gröbner bases and toric ideals......Page 490
Sturmfels\' correspondence......Page 492
Polytopal complexes and regular triangulations......Page 499
Central and normal fans as regular triangulations......Page 500
Shellings, flips and face vectors......Page 504
Polytopality via regular triangulations......Page 513
Exercises......Page 520
Bibliography......Page 522
Index......Page 524