Computational search of small point sets with small rectilinear crossing number

Let $\text{crs}(K_n)$ be the minimum number of crossings over all rectilinear drawings of the complete graph on $n$ vertices on the plane. In this paper we prove that $\text{crs}(K_n)<0.380473\left(\genfrac{}{}{0px}{}{n}{4}\right)+\mathrm{\Theta }(n^3)$; improving thus on the previous best known upper bound. This is done by obtaining new rectilinear drawings of $K_n$ for small values of $n$, and then using known constructions to obtain arbitrarily large good drawings from smaller ones. The “small” sets where found using a simple heuristic detailed in this paper.