Improved Bounds for the Number of (<=k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n

Balogh, József and Salazar, Gelasio (2004) Improved Bounds for the Number of (<=k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 25-35 (Official URL:

Full text not available from this repository.


We use circular sequences to give an improved lower bound on the minimum number of (<=k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number $\square(S)$ of convex quadrilaterals determined by the points in S is at least $0.37553\binom{n}{4} + O(n^3)$. This in turn implies that the rectilinear crossing number $\overline{\hbox{\rm cr}}(K_n)$ of the complete graph K_n is at least $0.37553\binom{n}{4} + O(n^3)$. These improved bounds refine results recently obtained by Ábrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_4
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:564

Repository Staff Only: item control page


B. M. Ábrego and S. Fernández-Merchant, A lower bound for the rectilinear crossing number, Manuscript (2003).

O. Aichholzer, F. Aurenhammer, and H. Krasser, On thw crossing number of complete graphs, Proc. 18th Ann. ACM Symp. Comp. Geom., Barcelona, Spain (2002), 19-24.

N. Alon and E. Györi, The number of small semispaces of a finite set of points in the plane, J. Combin. Theory Ser. A 41 (1986), 154-157.

A. Andrzejak, B. Aronov, S. Har-Peled, R. Seidel, and E. Welzl, Results on k-sets and J-facets via continuous motion, Proc. 14th Ann. ACM Sympos. Comput. Geom. (1998), 192-198.

J. Balogh and G. Salazar, On k-sets, convex quadrilaterals, and the rectilinear crossing number of K_n. Manuscript (2004). Submitted.

A. Brodsky, S. Durocher, and E. Gethner, Toward the Rectilinear Crossing Number of K_n: New Drawings, Upper Bounds, and Asymptotics, Discrete Math. 262 (2003), 59-77.

A. Brodsky, S. Durochner, and E. Gethner, The rectilinear crossing number of K_10 is 62. Electron. J. Combin. 8 (2001), Research Paper 23, 30 pp.

T. Dey, Improved bounds on planar k-sets and related problems, Discr. Comput. Geom. 19 (1998), 373-382.

H. Edelsbrunner, N. Hasan, R. Seidel, and X.J. Shen, Circles through two points that always enclose many points, Geometriae Dedicata 32 (1989), 1-12.

P. Erdös and R. K. Guy, Crossing number problems, Amer. Math. Monthly 80 (1973), 52-58.

P. Erdös, L. Lovász, A. Simmons, and E. G. Strauss, Dissection graphs of planar points sets, A Survey of Combinatorial Theory, North Holland, Amsterdam (1973), 139-149.

J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A 29 (1980), 220-235.

L. Lovász, K. Vesztergombi, U. Wagner, and E. Welzl, Convex Quadrilaterals and k-Sets. Microsoft Research Technical Report MSR-TR-2003-06 (2003).

R. E. Pfiefer, The historical development of J. J. Sylvester's problem, Math. Mag. 62 (1989), 309-317.

J. Spencer and G. Tòth, Crossing numbers of random graphs, Random Structures and Algorithms 21 (2003), 347-358.

E. R. Scheinerman and H. S. Wilf, The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability, Amer. Math. Monthly 101 (1994), 939-943.

J. J. Sylvester, On a special class of questions on the theory of probabilities, Birningham British Assoc., Report35 (1865) 8-9.

G. Tóth, Point sets with many k-sets, Discr. Comput. Geom. 26 (2001), 187-194.

U. Wagner, On the rectilinear crossing number of complete graphs, Proc. 14th ACM-SIAM Sympos. Discr. Alg. (2003), 583-588.

E. Welzl, More on k-sets of finite sets in the plane, Discr. Comput. Geom. 1 (1986), 95-100.

E. Welzl, Entering and leaving j-facets, Discr. Comput. Geom. 25 (2001), 351-364.

A. White and L. W. Beineke, Topological graph theory. In Selected Topics in Graph Theory (L.W. Beineke and R.J. Wilson, eds.), pp. 15-49. Academic Press (1978).