Abstract
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\(O(\sqrt n )\). 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\(\Omega (\sqrt n )\) 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 2) 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 2). In the second case we obtain a bound of order\(O(\min \{ m^{{3 \mathord{\left/ {\vphantom {3 4}} \right. \kern-\nulldelimiterspace} 4}} n^{{5 \mathord{\left/ {\vphantom {5 8}} \right. \kern-\nulldelimiterspace} 8}} \log ^{{1 \mathord{\left/ {\vphantom {1 4}} \right. \kern-\nulldelimiterspace} 4}} n, n\sqrt m \} )\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Alexander: Geometric methods in the study of irregularities of distribution,Combinatorica 10 (1990), 115–136.
B. Aronov, P. Erdős, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach, andL. J. Schulman: Crossing Families.Combinatorica 14 (1994), 127–134; also Proc. Seventh Annual Sympos. on Comp. Geom., ACM Press, New York (1991), 351–356.
N. Alon, M. Katchalski, andR. Pulleyblank: The maximum size of a convex polygon in a restricted set of points in the plane,Discrete Comput. Geom.,4 (1989), 245–251.
K. Ball: Volume ratios and a reverse isoperimetric inequality,J. London Math. Soc. (2)44 (1991), 351–359.
J. Beck: On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry,Combinatorica 3 (3–4) (1983), 281–297.
H. Edelsbrunner, P. Valtr, andE. Welzl: Cutting dense point sets in half, Proc. Tenth Annual Symp. on Comp. Geom., Stony Brook, ACM Press (1994), 203–210; also to appear inDiscrete Comput. Geom.
L. Fejes Tóth:Regular figures, Pergamon Press, Oxford 1964.
J. Pach: Notes on Geometric Graph Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (ed. R. Pollack and W. Steiger), Vol. 6 (1991), 273–285.
E. Szemerédi andW. T. Trotter: Extremal problems in discrete geometry,Combinatorica 3 (3–4) (1983), 381–392.
P. Valtr: Convex independent sets and 7-holes in restricted planar point sets,Discrete Comput. Geom.,7 (1992), 135–152.
P. Valtr: On mutually avoiding sets, to appear in The Mathematics of Paul Erdős (R.L. Graham and J. Nešetřil, eds.), Springer.
P. Valtr: Planar point sets with bounded ratios of distances, PhD. thesis, Free Univ. Berlin (1994).
Author information
Authors and Affiliations
Additional information
The work on this paper was supported by Czech Republic grant GAČR 201/94/2167, by Charles University grants No. 351 and 361, by “Deutsche Forschungsgemeinschaft”, grant We 1265/2-1, and by DIMACS.
Rights and permissions
About this article
Cite this article
Valtr, P. Lines, line-point incidences and crossing families in dense sets. Combinatorica 16, 269–294 (1996). https://doi.org/10.1007/BF01844852
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01844852