Abstract

Let PP be a set of points in general position in the plane. Join all pairs of points in PP with straight line segments. The number of segment-crossings in such a drawing, denoted by $\crg(P)$, is the \emph{rectilinear crossing number} of PP. A \emph{halving line} of PP is a line passing though two points of PP that divides the rest of the points of PP in (almost) half. The number of halving lines of PP is denoted by h(P)h(P). Similarly, a kk\emph{-edge}, 0≤k≤n/2−10\leq k\leq n/2-1, is a line passing through two points of PP and leaving exactly kk points of PP on one side. The number of (≤k)(\le k)-edges of PP is denoted by E≤k(P)E_{\leq k}(P) . Let $\rcr(n)$, h(n)h(n), and E≤k(n)E_{\leq k}(n) denote the minimum of $\crg(P)$, the maximum of h(P)h(P), and the minimum of E≤k(P)E_{\leq k}(P) , respectively, over all sets PP of nn points in general position in the plane. We show that the previously best known lower bound on E≤k(n)E_{\leq k}(n) is tight for k<⌈(4n−2)/9⌉k<\lceil (4n-2) /9\rceil and improve it for all k≥⌈(4n−2)/9⌉k\geq \lceil (4n-2) /9 \rceil . This in turn improves the lower bound on $\rcr(n)$ from 0.37968(n4)+Θ(n3)0.37968\binom{n} {4}+Θ(n^{3}) to {277/729}\binom{n}{4}+Θ(n^{3})\geq 0.37997\binom{n}{4}+Θ(n^{3}).Wealsogivetheexactvaluesof. We also give the exact values of \rcr(n)and and h(n) forall for all n\leq27.Exactvalueswereknownonlyfor. Exact values were known only for n\leq18andodd and odd n\leq21forthecrossingnumber,andfor for the crossing number, and for n\leq14andodd and odd n\leq21$ for halving lines.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.