Lectures on Discrete Geometry (Jiri Matousek)

Errata and remarks

• P. 8 bottom, the Bonnice-Klee theorem should read "Any k-interior point of conv(X) is a k-interior point of conv(Y) for some Y\subseteq X with at most max(2k,d+1) points, where x is called a k-interior point of a set C if x lies in the relative interior of the convex hull of some k+1 affinely independent points of Y." (Noted by Sergio Cabello.)
• P. 9, Exercise 4(b), it is to be proved f(conv(X))=conv(f(X)). (Noted by Sergio Cabello.)
• P. 21, 2nd line from below: BU should be ZU. (Noted by Sergio Cabello.)
• P. 22, l. 16, Example 2.1.3 should be Proposition 2.1.3. (Noted by Sergio Cabello.)
• P. 23, the conclusion of the proof of Theorem 2.2.2 is oversimplified; the point v' need not lie in P. One needs to rewrite v'=\sum_{j=1}^{i-1}(\alpha_j+1)\gamma_j z_j + \gamma_i\alpha_i w, and reduce once more; that is, to consider v'' = \sum_{j=1}^{i-1} fract.part((\alpha_j+1)\gamma_j)z_j +\gamma_i\alpha_i w, obtaining \gamma_i=0 as before. (Noted by Sergio Cabello.)
• P. 23 (what an unfortunate page!), Bibliography and Remarks, 3rd line: An assumption is omitted, namely, that C has to be a star body, i.e. a compact set containing 0 in the interior and such that x\in C implies tx\in C for all t\in[0,1]. A few lines below: "det(Lambda) > D" should be "det(Lambda) < D". (Noted by Sergio Cabello.)
• P. 49, l. 6, "at most 8 distinct curves \gamma_{ij}" better "at most 8 of the curves \gamma_{ij}" (some of the curves may conicide)
• P. 53, l. 10 from below: 2^{r-1}/16 should be n2^{r-1}/8. (Noted by Micha Sharir and his students.)
• P. 56, 2nd line below the picture, P should be E. (Noted by Nati Linial.)
• P. 57, line 6: "closed under REMOVING edges" (instead of addding). (Noted by Uli Wagner.)
• P. 70 Exercise 4.5.2, O(n\sqrt m + m) (instead of O(n\sqrt m + n)). (Noted by Sergio Cabello.)
• P. 77, picture, the top vertex of the front square should be 1423 (rather than 1342). (Noted by Petr Skovron.)
• P. 84, line 2, < \sigma,\leq > 1 should be < \sigma, x >\leq 1.
• P. 89, the elements 15 and 235 shouldn't be connected in the face lattice, while 35 should be connected to 235. (Noted by Yoshio Okamoto and by Tomasz Gdala.)
• P. 97 picture, the labels gamma_5 and gamma_6 should be gamma_4 and gamma_5. (Noted by Petr Skovron.)
• P. 98, last line of the proof of Theorem 5.4.5, the binomial coefficient should be n-k-1 choose k-1. (Noted by Micha Sharir and his students.)
• P. 101, in the sentence at lines 6-8, the words "upwards" and "downwards" should be interchanged. (Noted by Yoshio Okamoto.)
• P. 102, last line of the first paragraph, "simple" should be "simplicial". (Noted by Micha Sharir and his students.)
• P. 108 middle, the matrix A should be (d+1)x n, instead of d x n. (Noted by Yoshio Okamoto.)
• P. 123, last line of exercise 5.7.2, n^k should be n^{k+1}. (Noted by Uli Wagner.)
• P. 131, as I've learned from Ricky Pollack, Oleinik and Petrovskii only proved bounds for the sum of Betti numbers (and in particular, for the number of connected components) of an algebraic set, i.e. the intersection of the zero sets of n polynomials, under the additional assumption that these zero sets are smooth hypersurfaces. Thom and Milnor obtained more general bounds but still for algebraic sets. Sign patterns were explicitely considered only later (but a reduction of this problem to the number of connected components of a suitable algebraic set is not very hard).
• P. 139, Exercise 2(c): There are actually quite simple examples (which I've overlooked, unfortunately) showing that the number of intersection graphs of convex sets is at least 2^{const. n^2}. Recently Pach and Toth ("How many drawings are there?", manuscript, 2002) determined the right constant in the exponent: the number is 2^{(3/8+o(1))n^2}, for both intersection graphs of planar convex sets and intersection graphs of planar curves.
• P. 159, above the second displayed formula from below, t(r/n) should be t(n/r). (Noted by Uli Wagner.)
• P. 178 middle, definition of "nonrepetitive segment", the index of the last symbol a_{i+k} should be i+k-1 (noted by Pavel Valtr)
• P. 205 line 2: T_3(X) is always nonempty for a (2d+3)-point set in dimension d. A correct formulation is "for a set X in R^d, where d is a part of input, is NP-complete." (Noted by Emo Welzl.)
• P. 218 Lemma 9.3.2: the sets C_i should also be compact, for otherwise, the implication (i)=>(ii) need not hold. (Noted by Uli Wagner.)
• P. 241, bottom displayed formula, 2er ln r r^{-C/4} should be 2eCr ln r r^{-C/4}. (Noted by Guy Even.)
• P. 250 l. -18: the visibility regions in the cited example from [Val99b] occupy 5/9 of the gallery (rather than 1/2). (Noted by Pavel Valtr)
• P. 275, the line lambda_v in the upper picture should be drawn one "floor" lower, so that the marked vertices lie on the middle level. (Noted by Micha Sharir.)
• P. 286, in the outline of the proof of the improved k-set bound in dimension 3, n_p should be replaced by n throughout. Moreover, for the case where the chains C_1 and C_2 do not cross, we still need to distinguish two subcases: If both C_1 and C_2 end with infinite rays on both sides, then the argument in the outline can be applied. The other case, where at least one of C_1, C_2 ends with at least one bounded edge, needs to be accounted for separately: there are at most c_p n such pairs. (Noted by Uli Wagner.)
• P. 291, Berge's Strong Perfect Graph Conjecture has recently been proved by Chudnovsky, Robertson, Seymour, and Thomas, by graph-theoretic (as opposed to polyhedral) methods. See Chvatal's web page about it.
• P. 294 Exercise 2: K should be a MAXIMAL clique. (Noted by Robert Samal.)
• P. 300, 3rd line from the bottom: A+B should be (1-t)A+tB. (Noted by Robert Samal.)
• P. 301, end of "Bibliography and Remarks", the sets should be A,B,K_3,K_4,...,K_n and the left-hand side of the inequality should be V(A,B,K_3,...,K_n)^2. (Noted by Robert Samal.)
• P. 305 bottom, c_1 equals (1/(n+1))(h(b)-h(a)) (a and b exchanged). (Noted by Robert Samal.)
• P. 308 line -14 the right bar of the absolute value sign is missing. (Noted by Nati Linial.)
• P. 312, 4th line below the first picture, 2\pi e/n should be \pi e/2n. (Noted by Robert Samal.)
• P. 314 ex. 2, the integral should range over R^n, not R^d. (Noted by Nati Linial.)
• P. 315, 5 lines below Theorem 3.1.2, c^N should be c^n. (Noted by Robert Samal.)
• P. 317, the second paragraph ("By more refined consideration...") is oversimplified and confusing at best. Here is an attempt at a correct concise explanation: "By more refined consideration, one can improve the lower bound to approximately the square of the quantity just given. Having generated the query points x_1,...,x_N for B^n, we check that for K=conv {+e_1,-e_1,...,+e_n,-e_n,+x_1^0,-x_1^0,...,+x_N^0, -x_N^0}, with x_i^0=x_i/||x_i||, the oracle is free to give the same answers as those for B^n, and the same holds for the dual body K^*. A deep result (the inverse Blaschke-Santalo inequality) states that vol(K)vol(K^*) > c^n/n! for any centrally symmetric n-dimensional convex body K, with an absolute constant c>0, and together with Theorem 13.2.1 this yields the appropriate lower bound for vol(K^*)/vol(K). This improvement is interesting because for symmetric convex bodies it almost matches the performance of the best known algorithm." (Noted by Nati Linial.)
• P. 318, third line from below, "distance at most 1/n from S'" should be "distance at most 1/n from x". (Noted by Man-Cho A. So.)
• P. 319, we should (and may) also assume that N>2n, say, so that the formula defining k yields a value below n. (Noted by Robert Samal.)
• P. 323, last line, the convex hull of the y^{(i)} is not a crosspolytope; one should speak about +y^{(i)} and -y^{(i)} or phrase the argument a bit differently. (Noted by Nati Linial.)
• P.324 line 11, "n special points" (instead of "d special points"). (Noted by Nati Linial.)
• P. 328 Exercise 3: the last inequality in (b) should be vol(E) <= max(vol(E_1),vol(E_2)), rather than vol(E) >= min(vol(E_1),vol(E_2)). (Noted by Kasturi Varadarajan.)
• P. 329 l. -12, the exponent of epsilon should be +2, rather than -2.
• P. 332 l. 6 (2nd line in the displayed formula), "=" should be "<=" (noted by Rados Radoicic)
• P. 333, Prop. 14.2.1, R^d should be R^n. (Noted by Nati Linial.)
• P. 340, 2nd line of the last paragraph, "-lambda^2" in the exponent should be "lambda^2".
• P. 343, above Lemma 14.4.2, "2k facets" should be "2n facets". (Noted by Robert Samal.)
• P. 348, Exercise 1, "Hammer" should be "Hanner" (my apologies to him).
• For a new survey on the topics of Chapter 15 see a handbook chapter by Piotr Indyk and me. Many open problems, with updates on recent progress, are listed in Open problems on embeddings of finite metric spaces from the "Workshop on Discrete Metric Spaces and Their Algorithmic Applications" held in Haifa, March 3-7, 2002.
• P. 361, notes to Section 15.2, 2nd paragraph from below, "16/epsilon^2" should be "4/epsilon^2". (Noted by Piotr Indyk.)
• P. 376 l. 11, "\mu_2/n" should be "n/\mu_2". (noted by Rados Radoicic.)
• P. 378 top, phi and eta are interchanged (in the definition, on the line below the 2nd displayed formula, and 4 lines below). Moreover, the D^2 factor in the definition of x_{uv} should be present in the second case and not in the first, and the inequality in the next line should be \rho^2(\eta)-D^2\rho^2(\varphi)\geq 0. Other ways of fixing the confusion with eta and phi are possible as well. (Noted by Mikhail Ostrovskii.)
• P. 407, Dvoretzky is misspelled (with "s" instead of "z").
• P. 409, hint to Exercise 2.1.4(c), n^{d+1} should be n^{-(d+1)}. (Noted by Sergio Cabello.)