|
Descripción
|
|
|---|---|
| We provide a new lower bound on the number of $(\leq k)$-edges of a set of $n$ points in the plane in general position. We show that for $0 \leq k \leq \lfloor\frac{n-2}{2}\rfloor$ the number of $(\leq k)$-edges is at least $$ E_k(S) \geq 3\binom{k+2}{2} + \sum_{j=\lfloor\frac{n}{3}\rfloor}^k (3j-n+3), $$ which, for $\lfloor\tfrac{n}{3}\rfloor\leq k\leq 0.4864n$, improves the previous best lower bound in \cite{bs-ibnks-05}. 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 $$ \Bigl(\frac{41}{108}+\varepsilon \Bigr) \binom{n}{4} + O(n^3) \geq 0.379688 \binom{n}{4} + O(n^3), $$ which improves the previous bound of $0.37533 \binom{n}{4} + O(n^3)$ in \cite{bs-ibnks-05} and approaches the best known upper bound $0.380559 \binom{n}{4} + \Theta(n^3)$ in \cite{af-dwfc-07}. 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 $\lcr(K_{19})=1318$ and $\lcr(K_{21})=2055$. Moreover we provide improved upper bounds on the maximum number of halving edges a point set can have. | |
|
Internacional
|
Si |
|
JCR del ISI
|
Si |
|
Título de la revista
|
DISCRETE COMPUT GEOM |
|
ISSN
|
0179-5373 |
|
Factor de impacto JCR
|
0,616 |
|
Información de impacto
|
|
|
Volumen
|
38 |
|
DOI
|
|
|
Número de revista
|
1 |
|
Desde la página
|
1 |
|
Hasta la página
|
14 |
|
Mes
|
JULIO |
|
Ranking
|
|