Lines,line-point incidences and crossing families in dense sets

LetP be a set ofn points in the plane. We say thatP isdense if the ratio between the maximum and the minimum distance inP is of order . A setC of line segments in the plane is calleda crossing family if the relative interiors of any two line segments ofC intersect. Vertices of line segments of a crossing familyC are calledvertices of C. It is known that for any setP ofn points in general position in the plane there is a crossing family of size with vertices inP. In this paper we show that ifP is dense then there is a crossing family of almost linear size with vertices inP.The above result is related to well-known results of Beck and of Szemerédi and Trotter. Beck proved that any setP ofn points in the plane, not most of them on a line, determines at least (n ²) different line. Szemerédi and Trotter proved that ifP is a set ofn points and is a set ofm lines then there are at mostO(m ^2/3 n ^2/3 +m+n) incidences between points ofP and lines of . We study whether or not the bounds shown by Beck and by Szemerédi and Trotter hold for any dense setP even if the notion of incidence is extended so that a point is considered to be incident to a linel if it lies in a small neighborhood ofl. In the first case we get very close to the conjectured bound (n ²). In the second case we obtain a bound of order .The work on this paper was supported by Czech Republic grant GAR 201/94/2167, by Charles University grants No. 351 and 361, by Deutsche Forschungsgemeinschaft, grant We 1265/2-1, and by DIMACS.