Abstract
Let be a set of points in general position in the plane. Join all pairs of points in with straight line segments. The number of segment-crossings in such a drawing, denoted by $\crg(P)$, is the \emph{rectilinear crossing number} of . A \emph{halving line} of is a line passing though two points of that divides the rest of the points of in (almost) half. The number of halving lines of is denoted by . Similarly, a \emph{-edge}, , is a line passing through two points of and leaving exactly points of on one side. The number of -edges of is denoted by . Let $\rcr(n)$, , and denote the minimum of $\crg(P)$, the maximum of , and the minimum of , respectively, over all sets of points in general position in the plane. We show that the previously best known lower bound on is tight for and improve it for all . This in turn improves the lower bound on $\rcr(n)$ from to {277/729}\binom{n}{4}+Θ(n^{3})\geq 0.37997\binom{n}{4}+Θ(n^{3})\rcr(n)h(n) n\leq27n\leq18n\leq21n\leq14n\leq21$ for halving lines.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.