Abstrakt
Let d and k be integers with 1kd-1. Let be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin.
We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in K. In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional nxxn grid is at least (nd(d-k)/(d-1)-epsilon) and at most O(nd(d-k)/(d-1)), where epsilon>0 is an arbitrarily small constant.
This nearly settles a problem mentioned in the book by Brass et al. (Research problems in discrete geometry, Springer, New York, 2005). We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover K.
We use these new results to improve the best known lower bound for the maximum number of point-hyperplane incidences by Brass and Knauer (Comput Geom 25(1-2):13-20, 2003). For d3 and epsilon(0,1), we show that there is an integer r=r(d,epsilon) such that for all positive integers n,m the following statement is true.
There is a set of n points in Rd and an arrangement of m hyperplanes in Rd with no Kr,r in their incidence graph and with at least ((mn)1-(2d+3)/((d+2)(d+3))-epsilon) incidences if d is odd and ((mn)1-(2d2+d-2)/((d+2)(d2+2d-2))-epsilon) incidences if d is even.