Comments on problems from the book





Section 1.4, Problem #4

A. Bezdek and W. Kuperberg constructed a convex pentagon with the property that any of the thinnest coverings of the plane by its congruent copies contains a crossing pair. In other words, the answer to question formulated to Problem 4 is yes, if in condition (2) instead of \'affine transformations\' we take \'congruences\'.
Bibliography: A. Bezdek and W. Kuperberg: Unavoidable crossings in a thinnest plane covering with congruent convex disks. Discrete Comput. Geom. 43 (2010), no. 2, 187–208.

Section 1.10, Problem #6

Chuanming Zong proved that the largest common value of roT(C) and roL(C) over all centrally symmetric convex bodies C in the plane is (2-sqrt(2))/(2+sqrt(2))~0.17157, which is attained if and only if C is an affinely regular hexagon.
Bibliography: Chuanming Zong: Simultaneous Packing and Covering in the Euclidean Plane II

http://www.math.pku.edu.cn:8000/var/preprint/7115.pdf


Section 2.1, Problem #5

X. Chen, J. Pach, M. Szegedy, and G. Tardos proved that for a fixed c and k, as n tends to infinity, a randomly and uniformly selected set of n points in the unit square almost surely has the property that no matter how we color its elements by c colors, we can find an axis-parallel rectangle such that all points within this rectangle are of the same color.
Bibliography: X. Chen, J. Pach, M. Szegedy, and G. Tardos:Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles, Random Structures and Algorithms, submitted.

Section 2.4, Problem #5

Mira Lee and Otfried Cheong proved that the Hadwiger number of Jordan regions can be arbitrarily high.
Bibliography: Otfried Cheong and Mira Lee.
The Hadwiger number of Jordan regions is unbounded.
Accepted for publication in Discrete & Computational Geometry.
Also at:
http://arxiv.org/PS_cache/cs/pdf/0702/0702079v1.pdf


Section 2.4, Problem #13

M. Naszodi proved that any family of pairwise touching homothetic copies of a centrally symmetric convex body in d-dimensional space consists of at most 2d+1 members.
Bibliography: M. Naszódi: On a conjecture of Karoly Bezdek and Janos Pach. On a conjecture of Károly Bezdek and János Pach. Period. Math. Hungar. 53 (2006), no. 1-2, 227–230.

Section 3.2, Problem #6

By a simple compactness argument, Naszódi showed that $H_d=\bar H_d$ for every $d$, that is, that for any fixed dimension, $d$, there is a $0<\lambda_d<1$ homothety ratio, such that each convex body $K$ in $\mathbb{R}^d$ can be covered by $H(d)$ translates of $\lambda_d K$. Here $H(d)$ is the maximum (over all convex bodies $K$ in $\mathbb{R}^d$) of the minimum number of translates of $int(K)$ that cover $K$.
Bibliography: Márton Naszódi: On the constant of homothety for covering a convex set with its smaller copies, Pro Mathematica, Vol. 24, No. 47-48 (2010), pp. 113-119.

Section 5.11, Problem #1

We call a point set rational if all pairwise distances between their elements are rational.

Theorem 1: Every rational set of the plane has only finitely many points in common with an algebraic curve defined over R, unless the curve has a component which is a line or a circle.

Theorem 2: If a rational set S has infnitely many points on a line or on a
circle, then all but 4 resp. 3 points of S are on the line or on the circle.
Bibliography: József Solymosi and Frank de Zeeuw: On a question of Erdős and Ulam. Discrete Comput. Geom. 43 (2010), no. 2, 393-401.

Section 6.1, Problem #10

Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, and Micha Sharir
considered the problem of bounding the maximum possible number
fk,d(n) of k-simplices that are spanned by a set of n
points in Rd
and are similar to a given simplex. They showed
f2,3(n)=O(n13/6) and
f2,5(n)=O(n8/3).
They also gave upper bounds for
fd-2,d(n) and
fd-1,d(n).
Bibliography: Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, Micha Sharir.
Similar Simplices in a d-Dimensional Point Set.
To appear in SoCG 2007.

Section 6.1, Problem #13

It was shown by V. Cortier, X. Goaoc, Mira Lee, and Hyeon-Suk Na that the number of maximally repeated subpatterns in d-dimensional euclidean space, which was conjectured
to be polynomial, is in fact Θ(2n/2)in the worst case, regardless of the dimension d.
Bibliography: V. Cortier,X. Goaoac, M. Lee, and
H.-S. Na: A note on maximally repeated sub-patterns of a point set. See:
>http://hal.inria.fr/view_by_stamp.php?label=LORIA&langue=en&action_todo=view&id=inria-00070247&version=1

Section 6.2, Problem #12

Adrian Dumitrescu, Micha Sharir, and Csaba D. Toth proved that the
maximum number of unit area triangles determined by n points on
the plane is O(n2+6/19), i.e., approximately
O(n2.3158), improving on the O(n7/3) result
by Pach and Sharir from 1992.
Bibliography: Adrian Dumitrescu, Micha Sharir, and Csaba D. Toth.
Extremal problems on triangle areas in the plane and three-space.
Manuscript, 2007.

Section 6.2, Problem #14

Adrian Dumitrescu and Csaba D. Toth improved the lower bound for the minimum number of distinct areas of all triangles determined by n noncollinear points in the plane to 0.4473n (from 0.4142n).


Subsequently, Rom Pinchasi has completely settled the conjecture: He proved that there always exists a point pair contained in at least the lower integer part of (n-1)/2 triangles of ditinct areas.
Bibliography: Adrian Dumitrescu and Csaba D. Toth.
Distinct triangle areas in a planar point set. Proc. 12th Conf. on Integer Programming and Optimization (Ithaca, NY, 2007), LNCS, Springer, to appear.

Rom Pinchasi. The minimum number of distinct areas of triangles determined by a set of n points in the plane. SIAM J. Discrete Mathematics, to appear.

Section 6.2, Problem #16

Adrian Dumitrescu and Csaba D. Toth showed that

1. the number of unit volume tetrahedra determined by n points in 3-space is O(n7/2), and they constructed examples for which this number is at least n3loglog n;

2. the maximum number of minimum volume tetrahedra determined by n points in 3-space is of the order of magnitude of n3;

3. the order of magnitude of the minimum number of distinct volumes of tetrahedra determined by n noncoplanar points in 3-space is linear in n.
Bibliography: Adrian Dumitrescu and Csaba D. Toth.
On the number of tetrahedra with minimal, unit, and distinct volumes in three-space.
Proc. 18th ACM-SIAM Sympos. on Discrete Algorithms (New Orleans, LA, 2007), ACM Press, pp. 1114-1123.

Section 7.3, Problem #13

Noam Elkies proved that for k=5,7,9,...:
tkorchard(n) ≥
cknlogk2k (an improvement on the
exponent).
Bibliography: Noam Elkies.
On some points-and-lines problems and configurations.

http://arxiv.org/PS_cache/math/pdf/0612/0612749v1.pdf


Section 8.2, Problem #1

Szekeres and Peters verified the conjecture for
r=6.
Bibliography: G. Szekeres and L. Peters,
Computer solution to the 17 point Erdos-Szekeres problem.
ANZIAM Journal 48 (2006), 151-164.

Section 8.2, Problem #5

Let g(9) denote the smallest integer g such that any set of g points in general position in the plane has 9 points that form the vertex set of convex nonagon. (It is known that g(9)<=1717.)

Tobias Gerken showed that any set of at least g(9) points in general position has 6 vertices that span an empty convex hexagon.

Carlos Nicolas independently proved a weaker but finite upper bound for the maximum number of points that can be given without spanning an empty convex hexagon. An alternative presentation was given by Pavel Valtr.

Vitaliy Koshelev improved the above bounds by showing that any set of at least 463 points in general position in the plane spans an empty convex hexagon.
Bibliography: V. A. Koshelev: The Erdos-Szekeres problem in combinatorial geometry, Electronic Notes in Discrete Mathematics
29 (2007), 175-177.

C. M. Nicolas: The empty hexagon theorem, Discrete and Computational Geometry 38 (2007), 389-397.

See item 56 on

http://kam.mff.cuni.cz/~valtr/publications.html

P. Valtr: On empty hexagons, in: Surveys on Discrete and Computational Geometry -- Twenty Years Later (J. E. Goodman et al., eds.), Contemporary Mathematics 453, Amer. Math. Soc., Providence, RI, 2008, 433-441.

Section 8.2, Problem #6

Let X be a configuration of points no three of which lie on the
same line and no two of which have the same x-coordinate.
A subset P = {p1,...,pk} of X is open in X if no point of X lies above the polygon p1p2...pk.
Valtr proved that there exists an integer g(k,l) such that every
set X with at least g(k,l) points contains an open k-cap or
an open l-cup. Cerny gave a simpler proof and better recurrences for this function. Estimate g(k,l).

Note that Valtr's result immediately implies that Conjecture 6 is true.
Bibliography: P. Valtr. Open caps and cups in planar point sets.
To appear in Discrete Computational Geometry.


J. Cerny. A simple proof for open cups and caps.
http://iti.mff.cuni.cz/series/files/iti271.pdf

Section 8.5, Problem #1

Xianglin Wei and Ren Ding settled the special case r=3 by proving that I(3)=9.
Bibliography: Xianglin Wei and Ren Ding.
On the existence of a point subset with 3 interior points. Manuscript.

Section 8.5, Problem #6

Let U(n) denote the smallest integer such that every set of n points in general position in the plane permits a convex decomposition with at most U(n) faces.

J. Garc´ıa-L´opez and C. M. Nicol´as disproved the conjecture by showing that for n>3, we have U(n)>(12/11)n-2.

On the other hand, V. Neumann-Lara, E. Rivera-Campo, and J. Urrutia proved that U(n)<(10n-18)/7.
Bibliography: J. Garc´ıa-L´opez and C. M. Nicol´as: Planar Point Sets with Large Minimum Convex Partition, Proc. 22nd European Workshop on Computational Geometry, 2006 (EWCG 2006, Delphi, March 27-29, 2006), 51-54.http://delaunay.tem.uoc.gr/~mkaravel/ewcg06/papers/12.pdf

V. Neumann-Lara, E. Rivera-Campo, J. Urrutia, A note on convex decompositions of a set of points in the plane, Graphs and Combinatorics 20(2), 2004, 223-231.

Section 9.2, Problem #6

Chalopin, Gonçalves, and Ochem proved that the vertices of any planar graph can be represented by \'pseudo-segments,\' that is, by continuous arcs in the plane, such that (1) if two vertices u and v are connected by an edge, then the corresponding arcs have precisely one point in common, at which they properly cross, and (2) if u and v are not connected, then the corresponding arcs are disjoint.
Bibliography: J. Chalopin, D. Gonçalves, and P. Ochem: Planar graphs are in 1-STRING, in: Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 609-617, ACM, SIAM, 2007.

Section 9.4, Problem #1

M. Pelsmayer, M. Schaefer, and D. Stefankovic constructed several graphs whose odd-crossing numbers and crossing numbers do not coincide. However, it is still possible (even likely?!) that the pair-crossing number of every graph is the same as its crossing number.

A somewhat better construction was found by Geza Toth, who also noticed that Valtr's proof [Va05] actually gives that the crossing number of any graph whose pair crossing number is k is at most O(k2/log2k).
Bibliography: Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel (2006) Odd Crossing Number Is Not Crossing Number. In: Graph Drawing 2005, LNCS 3843 (2006), 386-396.

G. Tóth. Note on the pair-crossing number and the odd-crossing Number, Discrete Comput. Geom. 39 (2008), no. 4, 791–799.

Section 9.4, Problem #3

O. Aichholzer, J. Garcia, D. Orden, and P. Ramos proved that the limit kappa is at least 41/108+epsilon>0.379631. This bound was subsequently improved by B. M. Ábrego, J. Balogh, S. Fernández-Merchant, J. Leańos, and G. Salazar.

On the other hand, B. M. Ábrego and S. Fernández-Merchant established the upper bound 0.380559.
Bibliography: O. Aichholzer, J. Garcia, D. Orden, and P. Ramos: New lower bounds for the number of (<=k)-edges and the rectilinear crossing number of Kn Discrete Comput. Geom. 38 (2007), no. 1, 1–14.

M. Ábrego and S. Fernández-Merchant. Geometric
drawings of Kn with few crossings. Journal of Combinatorial Theory, Series A 114 (2007) 373-379.

B. M. Ábrego, J. Balogh, S. Fernández-Merchant, J. Leańos, and G. Salazar. An extended lower bound on the number of (≤k)-edges to generalized configurations of points and the pseudolinear crossing number of Kn
J. Combin. Theory Ser. A 115 (2008), no. 7, 1257–1264.

Section 9.5, Problem #6

Let h = h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. It can be shown that Ω(n3/2) ≤ h(n) ≤ O(n2/log1/4 n).
Bibliography: J. Kynčl and P. Valtr: On edges crossing few other edges in simple topological complete graphs, Discrete Math. 309 (2009), no. 7, 1917–1923.

Section 9.6, Problem #4

For every ε> 0 and for every positive integer t, there exist δ > 0 and a positive integer n0 such that every
topological graph with n ≥ n0 vertices, at least n1+ε edges, and no pair of edges intersecting
in more than t points, has at least nδ pairwise intersecting edges.
Bibliography: J. Fox and J. Pach: Coloring Kk-free planar intersection graphs, manuscript, 2007.

Section 10.2, Problem #5

For the minimum number of bends of a polygon that covers the d-dimensional lattice cube of side length n, S. Bereg, P. Bose, A. Dumitrescu, F. Hurtado, and P. Valtr
established the lower bound
(1 + 1/d) nd-1 - O(nd-2)
and the upper bound
(1 + 1/(d-1)) nd-1 + O(nd-(3/2)).
Bibliography: S. Bereg, P. Bose, A. Dumitrescu, F. Hurtado, and P. Valtr,
Traversing a set of points with a minimum number of turns. 23rd
Annual Symposium on Computational Geometry, (SOCG '07), Gyeongju,
South-Korea, June 2007.

Section 11.2, Problem #6

Jaudon and Parlier proved that among all angles formed by triples of n points
in the plane there is an angle of at most pi/n.
Bibliography: Ghislain Jaudon and Hugo Parlier,
On angles formed by N points of the Euclidean and Hyperbolic planes.
Preprint arXiv:math/0603156