Abstract
We provide a new lower bound on the number of (≤ k)-edges of a set of n points in the plane in general position. We show that for \(0 \leq k \leq \lfloor({n-2})/{2}\rfloor\) the number of (≤ k)-edges is at least
which, for \(\lfloor {n}/{3}\rfloor\leq k\leq 0.4864n\), improves the previous best lower bound in [12]. As a main consequence, we obtain a new lower bound on the rectilinear crossing number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by n points in the plane in general position. We show that the crossing number is at least
which improves the previous bound of \(0.37533 \binom{n}{4} + O(n^3)\) in [12] and approaches the best known upper bound \(0.380559 \binom{n}{4} + \Theta(n^3)\) in [4]. The proof is based on a result about the structure of sets attaining the rectilinear crossing number, for which we show that the convex hull is always a triangle. Further implications include improved results for small values of n. We extend the range of known values for the rectilinear crossing number, namely by \(\mathop{\overline{\rm cr}}\nolimits(K_{19})=1318\) and \(\mathop{\overline{\rm cr}}\nolimits(K_{21})=2055\). Moreover, we provide improved upper bounds on the maximum number of halving edges a point set can have.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Aichholzer, O., Garcia, J., Orden, D. et al. New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of Kn. Discrete Comput Geom 38, 1–14 (2007). https://doi.org/10.1007/s00454-007-1325-8
Issue Date:
DOI: https://doi.org/10.1007/s00454-007-1325-8