On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$

Details On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$ On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$

2011-02-24

arxiv.org/abs/1102.5065v2

Mathematics

Combinatorics

Second version. In the first version, the PostScript version was OK (24 pages long), but in the generated PDF version (27 page

Scientific paper

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<\lceil (4n-2) /9\rceil $ and improve it for all $k\geq \lceil (4n-2) /9 \rceil $. This in turn improves the lower bound on $\rcr(n)$ from $0.37968\binom{n} {4}+\Theta(n^{3})$ to {277/729}\binom{n}{4}+\Theta(n^{3})\geq 0.37997\binom{n}{4}+\Theta(n^{3})$. We also give the exact values of $\rcr(n)$ and $h(n) $ for all $n\leq27$. Exact values were known only for $n\leq18$ and odd $n\leq21$ for the crossing number, and for $n\leq14$ and odd $n\leq21$ for halving lines.

Affiliated with

Also associated with

No associations

Rating

On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-87203