On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$
Bernardo M. Ábrego, M. Cetina, Silvia Fernández‐Merchant, Jesús Leaños, Gelasio Salazar · arXiv (Cornell University) · 2011
Let $P$ be a set of points in general position in the plane. Join all pairs of points in $P$ with straight line segments. The number of segment-crossings in such a drawing, denoted by $\crg(P)$, is the \emph{rectilinear crossing number} of $P$. A \emph{halving line} of $P$ is a line passing though two points of $P$ that divides the rest of the points of $P$ in (almost) half. The number of halving lines of $P$ is denoted by $h(P)$. Similarly, a $k$\emph{-edge}, $0\leq k\leq n/2-1$, is a line passing through two points of $P$ and leaving exactly $k$ points of $P$ on one side. The number of $(\le k)$-edges of $P$ is denoted by $E_{\leq k}(P) $. Let $\rcr(n)$, $h(n)$, and $E_{\leq k}(n) $ denote the minimum of $\crg(P)$, the maximum of $h(P)$, and the minimum of $E_{\leq k}(P) $, respectively, over all sets $P$ of $n$ points in general position in the plane. We show that the previously best known lower bound on $E_{\leq k}(n)$ is tight for $k