|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Matousek J. — Lectures on Discrete Geometry (some chapters) |
|
|
|
| Предметный указатель |
h-vector 102
Hadwiger — Debrunner (p,q)-problem 243
Hadwiger's transversal theorem 248
Hahn — Banach theorem 19
Halfspace 15
Halfspaces, VC-dimension 232 (10.3.1)
Hall's Marriage Theorem 225
Halving edge 252
Halving facet 252
Halving facet, interleaving lemma 262 (11.3.1)
Halving facet, interleaving lemma, application 263 268 271
Ham-sandwich theorem 26 (1.4.3)
Ham-sandwich theorem, application 209
Hammer polytope 325 (Ex.1)
Hamming cube 314
Hamming cube, embedding into  343
Harper's inequality 314
Height 287
Helly number 23
Helly order 250 (Ex.4)
Helly's theorem 21 (1.3.2)
Helly's theorem, application 23 (Ex.2) 24 25 83 188 191
Helly's theorem, colored 189 (Ex.2)
Helly's theorem, fractional 187 (8.1.1)
Helly's theorem, fractional, application 200 203 245
Helly's theorem, fractional, for line transversals 247 (10.6.2)
Helly-type theorem 248 250
Helly-type theorem for containing a ray 24 (Ex.6)
Helly-type theorem for lattice points 279 (Ex.7)
Helly-type theorem for line transversals 84 (Ex.9)
Helly-type theorem for separation 25 (Ex.9)
Helly-type theorem for visibility 25 (Ex.7)
Helly-type theorem for width 23 (Ex.4)
Hierarchically well-separated tree 364
High above 45
Higher-order Voronoi diagram 119
Hilbert space 333
Hirsch conjecture 94
Horton set 45
Horton set in  47
Hull, affine 13
Hull, convex 17
Hull, convex, algorithm 87 104
Hypergraph 203
Hyperplane 14
Hyperplane transversal 246 (10.6.1) 248
Hyperplane, linear 108
Hyperplanes, arrangement 124
I(m, n) (number of point-line incidences) 49
I(P, L) (point-line incidences) 49
Incidence matrix 223
Incidences 49
Incidences, point-circle 53 67 67 73 73 76
Incidences, point-curve 53
Incidences, point-line 49 (4.1.1)
Incidences, point-line, in the complex plane 52
Incidences, point-line, lower bound 57 (4.2.1)
Incidences, point-plane 53
Incidences, point-unit circle 50 55 57 73
Incidences, point-unit circle, upper bound 63 (Ex.2)
Independence number 274
Induced subgraph 274
Induced subhypergraph 203
Inequality, Alexandrov — Fenchel 284
Inequality, Blaschke — Santalo 301
Inequality, Brunn — Minkowski 280 (12.2.2)
Inequality, Brunn — Minkowski, application 311 313
Inequality, Brunn — Minkowski, dimension-free form 284 (Ex.5)
Inequality, Brunn's 280 (12.2.1)
Inequality, Cauchy — Schwarz 12
Inequality, Chebyshev's 229
Inequality, Harper's 314
Inequality, isoperimetric 312—316
Inequality, isoperimetric, reverse 316
Inequality, Jensen's 12
Inequality, Prekopa — Leindler 283 285
Inequality, Sobolev, logarithmic 315
Inradius 299 (13.2.2)
Inradius, approximation 302
Integer programming 35
Interpolation 115
Intersection graph 135 (Ex.2)
Inverse Blaschke — Santalo inequality 301
Isometric embedding 332
Isomorphic arrangements 131
Isomorphic arrangements, affinely 131
Isomorphic graphs 12
Isomorphism of hypegraphs 203
Isoperimetric inequality 312—316
Isoperimetric inequality, reverse 316
Jensen's inequality 12
John's lemma 305 (13.4.1)
John's lemma, application 324 326
Johnson — Lindenstrauss flattening lemma 334 (15.2.1)
Johnson — Lindenstrauss flattening lemma, application 340
Join 90
K(m, n) (number of edges of m cells) 51
k-edge 252
k-facet 251
k-flat 14
k-hole 44
k-hole, modulo q 47
k-interior point 20
k-partite hypergraph 203
k-set 251
k-set, polytope 258 (Ex.7)
k-uniform hypergraph 203
Kalai's conjecture 195
Kernel 24 (Ex.7)
KFAC(X, k) (number of k-facets) 252
Kirchberger's theorem 25 (Ex.9)
Knapsack problem 36
Koebe's representation theorem 93
Koevari — Sos — Turan theorem 69 (4.5.2)
Konig's edge-covering theorem 225 278
Krasnosel'skii's theorem 25 (Ex.7)
Kruskal — Hoffman theorem 278 (Ex.6)
Lagrange's four-square theorem 38 (Ex.2.3.1)
Laplace matrix 347
Largest empty disc, computation 119
Lattice basis theorem 34 (2.2.2)
Lattice constant 35
Lattice packing 35
Lattice point 29
Lattice point, computation 35
Lattice point, Helly-type theorem 279 (Ex.7)
Lattice, face 90
Lattice, general definition 33
Lattice, given by basis 32
Lattice, shortest vector 36
Lawrence's representation theorem 133
Lemma, cutting 70 (4.5.3) 72
Lemma, cutting, application 248
Lemma, cutting, for circles 75
Lemma, cutting, higher-dimensional 154 (6.5.3)
Lemma, cutting, lower bound 74
Lemma, cutting, proof 74 77 148 156 238
Lemma, Dvoretzky — Rogers 326 (14.6.2) 329
Lemma, Erdos — Szekeres 278 (Ex.4)
Lemma, Farkas 19 19 20
Lemma, first selection 200 (9.1.1)
Lemma, first selection, application 241
Lemma, first selection, proofs 202
Lemma, halving-facet interleaving 262 (11.3.1)
Lemma, halving-facet interleaving, application 263 268 271
Lemma, John's 305 (13.4.1)
Lemma, John's, application 324 326
Lemma, Johnson — Lindenstrauss flattening 334 (15.2.1)
Lemma, Johnson — Lindenstrauss flattening, application 340
Lemma, Levy's 317 (14.3.2) 318
| Lemma, Levy's, application 318 335
Lemma, Lovasz 263 (11.3.2)
Lemma, Lovasz, exact 264 266
Lemma, Lovasz, planar 265 (Ex.1)
Lemma, positive-fraction selection 218 (9.5.1)
Lemma, Radon's 21 (1.3.1) 23
Lemma, Radon's, application 22 23 212 232
Lemma, Radon's, positive-fraction 211
Lemma, regularity, for hypergraphs 214 (9.4.1)
Lemma, regularity, for hypergraphs, application 217 (Ex.2) 219
Lemma, regularity, Szemeredi's 214 217
Lemma, same-type 208 (9.3.1)
Lemma, same-type, application 211 219
Lemma, same-type, partition version 211
Lemma, second selection 202 (9.2.1)
Lemma, second selection, application 219 264
Lemma, second selection, lower bounds 206 (Ex.2)
Lemma, second selection, one-dimensional 206 (Ex.1)
Lemma, shatter function 228 (10.2.5)
Lemma, shatter function, application 234
Lens (in arrangement) 257 (Ex.5) 257
Level 76 136
Level, and higher-order Voronoi diagrams 119
Level, at most k, complexity 137 (6.3.1)
Level, complexity and k-sets 252
Level, for segments 179 (Ex.2)
Level, for triangles 176
Level, simplification 76
Levy's lemma 317 (14.3.2) 318
Levy's lemma, application 318
LinDep( ) 107
Line pseudometric 353 (Ex.2) 358
Line transversal 84 (Ex.9) 246 248
Line, balanced 265
Linear extension 285
Linear form 37 (Ex.4)
Linear hyperplane 108
Linear ordering 285
Linear programming 19
Linear programming, algorithm 94
Linear programming, duality 223 (10.1.2)
Linear subspace 13
Linearization 232
Lines, arrangement 50
LinVal() 107
Lipschitz function, concentration 317 (14.3.2)
Lipschitz mapping 316
Lipschitz mapping, extension 336
Lipschitz norm 332
Lipton — Tarjan theorem 62
LLL algorithm 36
Local density 363
Local theory of Banach spaces 309 315
Location, in planar subdivision 114
Loewner — John ellipsoid 307
Lovasz lemma 263 (11.3.2)
Lovasz lemma, exact 264 266
Lovasz lemma, planar 265 (Ex.1)
Lower bound theorem, generalized 104
Lower bound theorem, generalized, application 264
Lower envelope of curves 160 179
Lower envelope of segments 159
Lower envelope of segments, lower bound 163 (7.2.1)
Lower envelope of simplices 178
Lower envelope of triangles 175 (7.5.1) 178
Lower envelope, superimposed projections 184
LPS-expander 341
m( , n) (maximum number of edges for girth > ) 337
Manhattan distance see  -norm
Many cells, complexity 51 53 63 147
Mapping, affine 15
Mapping, bi-Lipschitz 332
Mapping, Lipschitz 316
Mapping, Lipschitz, extension 336
Mapping, Veronese 232
Marriage theorem, Hall's 225
Matching 222
Matching number See packing number
Matching polytope 273 277
Matrix, forbidden pattern 170
Matrix, incidence 223
Matrix, Laplace 347
Matrix, rank and signs 135 (Ex.4)
Matroid, oriented 133
MAXCUT problem 353 (Ex.5)
Maximum norm see  -norm
Measure concentration for Hamming cube 315 (14.2.3)
Measure concentration for sphere 310 (14.1.1)
Measure concentration, Gaussian 314 (14.2.2)
Measure on  , uniform 310
Measure on k-dimensional subspaces 317
Measure on SO(n) (Haar) 318
Measure, Gaussian 313
Measure, uniform 227
med(f) (median of f) 316
Medial axis transform 117
Median 25 316
Meet 90
Membership oracle 298 302
Method, double-description 87
Method, ellipsoid 352
Metric cone 105 349
Metric polytope 105
Metric space 331
Metric, line 353 (Ex.2) 358
Metric, of negative type 352
Metric, planar-graph 360
Metric, shortest-path 360
Metric, squared Euclidean, cone 349
Metric, tree 360 364 365 365 365
Milnor — Thom theorem 128 132
Minimum spanning tree 120 (Ex.5)
Minimum, successive 35
Minkowski sum 280
Minkowski — Hlawka theorem 35
Minkowski's second theorem 35
Minkowski's theorem 29 (2.1.1)
Minkowski's theorem for general lattices 33 (2.2.1)
Minor, excluded, and metric 360
Mixed volume 284
Molecular modeling 119
Moment curve 97 (5.4.1)
Monotone subsequence 278 (Ex.4)
Moore graph 341
Motion planning 114 119 184
Multigraph 11
Multiset 11
Nearest neighbor searching 114
Neighborhood, orthogonal 299
Nerve 189
Nonrepetitive segment 171
Norm 321
Norm,  333
Norm, 333
Norm, Lipschitz 332
Norm, maximum see -norm
Normal distribution 314 328
Number crossing 60
Number crossing and forbidden subgraph 62
Number crossing, odd 62
Number crossing, pairwise 62
Number matching see Packing number
Number packing 222
Number piercing see Transversal number
Number transversal 221
Number transversal, bound using  225 231
Number, algebraic 32 (Ex.4)
Number, chromatic 274
Number, clique 274
Number, fractional packing 222
|
|
|
| Реклама |
|
|
|
|
|
О проекте