|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Matousek J. — Lectures on Discrete Geometry (some chapters) |
|
|
|
| Предметный указатель |
Number, fractional transversal 222
Number, Helly 23
Number, independence 274
o(.) (asymptotically smaller) 11
Octahedron, generalized see Crosspolytope
Odd crossing number 62
odd-cr(G) (odd crossing number) 62
Oracle, membership 298 302
Order polytope 286 (12.3.2)
Order type 207 212
Order, Helly 250 (Ex.4)
Ordering 285
Ordering, linear 285
Orientation 207
Oriented matroid 133
Orthogonal neighborhood 299
Packing 222
Packing number 222
Packing, fractional 222
Packing, lattice 35
Pair, closest, computation 119
pair-cr(G) (pairwise crossing number) 62
Pairwise crossing edges 169
Pairwise crossing number 62
Pappus theorem 131
Paraboloid, unit 116
Parallel edges 169
Partially ordered set 285
Partition theorem 72
Partition, Radon 21
Partition, Tverberg 192
Patches, algebraic surface, lower envelope 181
Patches, algebraic surface, single cell 183 (7.7.2)
Path compression 169
Pattern on a variety 132
Pattern, sign, of polynomials 128
Pencil 129
Pentagon, similar copies 56 (Ex.9)
Perfect graph 274—279
Permanent, approximation 302
Permutahedron 79 87
Permutahedron, faces 95 (Ex.3)
Permutation, forbidden pattern 170
Perturbation argument 101
Planar-graph metric 360
Plane 14
Plane, Fano 51
Plane, projective 14
Plane, topological 133
Planes, incidences 53
Planning, motion 114 119
Point location 114
Point, exposed 96 (Ex.8)
Point, extremal 88 96 96
Point, k-interior 20
Point, lattice 29
Point, lattice, computation 35
Point, lattice, Helly-type theorem 279 (Ex.7)
Point, r-divisible 195
Point, Radon 21 25
Point, random, in ball 294
Point, Tverberg 192
Point-line incidences 49 (4.1.1)
Point-line incidences, in the complex plane 52
Points, random, convex hull 99 305
Polarity see Duality
Polygons, convex, union complexity 185
Polyhedral combinatorics 273
Polyhedron, convex 85
Polyhedron, H-polyhedron 84 (5.2.1)
Polymake 87
Polynomial factorization 36
Polynomial on Cartesian products 54
Polytope (convex) 85
Polytope (convex), almost spherical, number of facets 320 (14.4.2)
Polytope (convex), chain 291
Polytope (convex), combinatorial equivalence 90 (5.3.4)
Polytope (convex), cyclic 97 (5.4.3)
Polytope (convex), cyclic, dual 91
Polytope (convex), cyclic, universality 99 (Ex.3)
Polytope (convex), fat-lattice 106 (Ex.1)
Polytope (convex), graph 89
Polytope (convex), graph, connectivity 89 96
Polytope (convex), H-polytope 84 (5.2.1)
Polytope (convex), Hammer 325 (Ex.1)
Polytope (convex), integral cvirefex:hoffm-int 278
Polytope (convex), k-set 258 (Ex.7)
Polytope (convex), matching 273 277
Polytope (convex), metric 105
Polytope (convex), number of 135 (Ex.3)
Polytope (convex), order 286 (12.3.2)
Polytope (convex), product 106 (Ex.1)
Polytope (convex), realization 94 111 134
Polytope (convex), simple 91 (5.3.6)
Polytope (convex), simple, determined by graph 94
Polytope (convex), simplicial 91 (5.3.6)
Polytope (convex), spherical 121 (Ex.10)
Polytope (convex), stable set 277
Polytope (convex), symmetric, number of facets 324 (14.4.2)
Polytope (convex), traveling salesman 273
Polytope (convex), union complexity 185
Polytope (convex), V-polytope 84 (5.2.1)
Polytope (convex), volume, lower bound 303
Polytope (convex), volume, upper bound 297 (13.2.1)
Popular face 146
POSET 285
Position, convex 40
Position, general 15
Positive-fraction, Erdos — Szekeres theorem 211 (9.3.3) 213
Positive-fraction, Radon's lemma 211
Positive-fraction, selection lemma 218 (9.5.1)
Positive-fraction, Tverberg's theorem 211
Post-office problem 114
Power diagram 118
Prekopa — Leindler inequality 283 285
Prime in arithmetic progressions 58 (4.2.4)
Prime in ring 58
Prime number theorem 58
Primitive recursive function 167
Probabilistic method, application 61 65 74 137 143 148 176 229 253 266 318 328 334 338 355—360
Problem, art gallery 234 238
Problem, Busemann — Petty 295
Problem, decomposition, for algebraic surfaces 156
Problem, Gallai-type 221
Problem, Hadwiger — Debrunner, (p,q) 243
Problem, k-set 251
Problem, knapsack 36
Problem, post-office 114
Problem, set cover 225
Problem, subset sum 36
Problem, Sylvester's 51
Problem, UNION-FIND 169
Problem, Zarankiewicz 72
Prob[A] (probability) 11
Product, of polytopes 106 (Ex.1)
Programming, integer 35
Programming, linear 19
Programming, linear, algorithm 94
Programming, linear, duality 223 (10.1.2)
Programming, semidefinite 351 352
Projection, almost spherical 329
Projection, concentration of the length 334 (15.2.2)
Projection, polytopes obtained by 87 (Ex.2)
Projective plane 14
Projective plane, finite 51 70
Pseudocircles 256
Pseudodisc 185
Pseudolattice, pentagonal 56 (Ex.9)
Pseudolines 129 133
Pseudolines, arrangement 255
| Pseudometric, line 353 (Ex.2) 358
Pseudoparabolas 257 (Ex.5) 257
Pseudosegment, level in arrangement 255
Pseudosegments, cutting curves into 73 256 257 257
Pseudosegments, extendible 136 (Ex.5)
Purdy's conjecture 54
P[A] (uniform measure on $S^{n-l}) 310
QSTAB(G) 277
Quadratic residue 37
Quasi-isometry 333
r-divisible point 195
Radius, equivalent 280
Radon point 21 25
Radon's lemma 21 (1.3.1) 23
Radon's lemma, application 22 23 212 232
Radon's lemma, positive-fraction 211
Rainbow simplex 190
Ramsey's theorem 39
Ramsey's theorem, application 40 42 43 48 99 346
Random graph, second eigenvalue 352
Random point in ball 294
Random points, convex hull 99 305
Random rotation 317
Random subspace 317
Rank, and signs 135 (Ex.4)
Rational function on Cartesian product 55
Ray, Helly-type theorem 24 (Ex.6)
Real algebraic geometry 129
Realization of arrangement 134
Realization of polytope 94 111
Reay's conjecture 195
Reduced basis 36
Reg 152
reg(p) (Voronoi region) 113
Regular forest 30 (2.1.2)
Regular graph 12
Regular simplex 85
Regular simplex, volume 300
Regularity lemma for hypergraphs 214 (9.4.1)
Regularity lemma for hypergraphs, application 217 (Ex.2) 219
Regularity lemma, Szemeredi's 214 217
Relation, Dehn — Sommerville 103
Residue, quadratic 37
Restriction (of set system) 227
Reverse isoperimetric inequality 316
Reverse search 105
Ridge 88
Robot motion planning 114 119 184
Rotation, random 317
Ryser's conjecture 225
Same-type lemma 208 (9.3.1)
Same-type lemma, application 211 213 219
Same-type lemma, partition version 211
Same-type transversals 208
Sard's theorem 16
Searching, nearest neighbor 114
searching, reverse 105
Second eigenvalue of graph 347
Second eigenvalue of random graph 352
Second selection lemma 202 (9.2.1)
Second selection lemma, application 219 264
Second selection lemma, lower bounds 206 (Ex.2)
Second selection lemma, one-dimensional 206 (Ex.1)
Section, almost spherical, of convex body 322 (14.4.5) 325
Section, almost spherical, of crosspolytope 323 329
Section, almost spherical, of cube 320
Section, almost spherical, of ellipsoid 319 (14.4.1)
Segments, arrangement 127
Segments, intersection graph 135 (Ex.2)
Segments, level in arrangement 179 (Ex.2)
Segments, lower envelope 159
Segments, lower envelope, lower bound 163 (7.2.1)
Segments, Ramsey-type result 213 (Ex.5) 217
Segments, single cell 169
Segments, zone 145
Selection lemma, first 200 (9.1.1)
Selection lemma, first, application 241
Selection lemma, first, proofs 202
Selection lemma, positive-fraction 218 (9.5.1)
Selection lemma, second 202 (9.2.1)
Selection lemma, second, application 219 264
Selection lemma, second, lower bounds 206 (Ex.2)
Selection lemma, second, one-dimensional 206 (Ex.1)
Semialgebraic set 181
Semialgebraic set and VC-dimension 234
Semidefinite programming 351 352
Separation theorem 18 (1.2.4)
Separation theorem, application 19 82 304 350
Separation, Helly-type theorem 25 (Ex.9)
Separator theorem 62
Sequence, Davenport — Schinzel 160
Sequence, Davenport — Schinzel, asymptotics 167
Sequence, Davenport — Schinzel, decomposable 171
Sequence, Davenport — Schinzel, generalized 168 169
Sequence, Davenport — Schinzel, realization by curves 162 (Ex.1)
Set cover problem 225
Set system, dual 234
Set, almost convex 47 48
Set, brick 282
Set, convex 17 (1.2.1)
Set, convex independent 40 (3.1.1)
Set, convex independent, in grid 43 (Ex.2)
Set, defining 152
Set, dense 43
Set, dual 82 (5.1.3)
Set, Horton 45
Set, Horton, in  47
Set, k-set 251
Set, k-set, polytope 258 (Ex.7)
Set, partially ordered 285
Set, polar see Dual set
Set, semialgebraic 181
Set, semialgebraic, and VC-dimension 234
Set, shattered 227 (10.2.3)
Set, stable see Independent set
Sets, convex, intersection patterns 189
Sets, convex, transversal 243 (10.5.1)
Sets, convex, upper bound theorem 189
Sets, convex, VC-dimension 227
Seven-hole theorem 45 (3.2.2)
Shatter function 228
Shatter function lemma 228 (10.2.5)
Shatter function lemma, application 234
Shatter function, dual 231
Shattered set 227 (10.2.3)
Shattering graph 239 (Ex.5)
Shelling 103
Shortest vector (lattice) 36
Shortest-path metric 360
Sierksma's conjecture 196
Sign matrix, and rank 135 (Ex.4)
Sign pattern, of polynomials 128
Sign pattern, on a variety 132
Sign vector (of a face) 124
Similar copies (counting) 53 56
Simple arrangement 125
Simple k-packing 225 (Ex.4)
Simple polytope 91 (5.3.6)
Simple polytope, determined by graph 94
simplex 85 (5.2.3)
Simplex algorithm, randomized 94
Simplex, circumradius and inradius 299 (13.2.2)
Simplex, faces 89
Simplex, projection 87 (Ex.2)
Simplex, rainbow 190
Simplex, regular 85
Simplex, volume 300
Simplex, X-simplex 199
Simplices, lower envelope 178
Simplices, single cell 184
|
|
|
| Реклама |
|
|
|
|
|
|
|
|
О проекте