Combinatorial Geometry Open Problems



Index of Problems
Crossing Families
Empty Hexagons
Non-empty Strips


Crossing Families

RESEARCHER: Pavel Valtr
OFFICE: CoRE 411
Email:valtr@dimacs.rutgers.edu
DESCRIPTION: Consider N points in the plane so that no three points lie on a line. Draw a line segment between each pair of vertices. The open problem is this: How large a family of mutually crossing line segments must there be? We say two line segments cross if they intersect on their interiors (as opposed to at their endpoints.) In the figure to the right, there is a family of 3 mutually crossing line segments, but not a family of 4.

It has been shown that there must always be a family of size sqrt(N/12), but it is believed that there must always be families of much larger size as well. So, what is the largest exponent t so that among N points in the plane, no three on a line, one can always find a crossing family of at least cN^t line segments, for some fixed constant c>0? If you can find such a t bigger than 1/2, then you will have made a substantial contribution.


Empty Hexagons

RESEARCHER: Pavel Valtr
OFFICE: CoRE 411
Email:valtr@dimacs.rutgers.edu
DESCRIPTION: It is known that any set of at least 10 points in the plane, no three on a line, contains an empty pentagon (i.e., 5 points which are vertices of a convex pentagon whose interior contains none of the points). The figure on the right shows 9 points with no empty pentagon (the dotted lines are shown to help visualization). Horton (1983) constructed arbitrarily large sets of points in the plane with no "empty 7-gon". The following question of Erdos remains open: "Is there an integer N such that any set of at least N points in the plane, no three on a line, contains an empty hexagon (i.e., six vertices of a convex hexagon whose interior contains no point of the set)?" Could you at least find, for any sufficiently large integer K, an empty hexagon in any set of K^2 points in a square K by K, when the distance between any two points is at least 1/10, say. This could be easier, although there is an example of such restricted sets with no empty heptagon.


Non-empty Strips

RESEARCHER: Pavel Valtr
OFFICE: CoRE 411
Email:valtr@dimacs.rutgers.edu
DESCRIPTION: Consider a set S of N^2 points inside a disk bounded by a circle C of length N, such that the distance between any two points of S is at least 1/100, say. Let A be a set of N^2 points distributed equidistantly along C. It is known that for at least c·N^4 pairs a,b of points of A, there is a point of S at distance at most 1/N from the line ab (c>0 is a positive constant). Is there a positive constant d>0 such that for at least d·N^4 pairs a,b of points of A, there are at least two points of S at distance at most 1/N from the line ab?




Back to main page