On the structure of sets attaining the rectilinear crossing number
Oswin Aichholzer, David Orden, Pedro A. Ramos · 2006
We study the structural properties of the point configurations attaining the rectilinear crossing number cr(Kn), that is, those n-point sets that minimize the number of crossings over all possible straight-edge embeddings of Kn in the plane. As a main result we prove the conjecture that such sets always have a triangular convex hull. The techniques developed allow us to show a similar result for the halving-edge problem: For any n there exists a set of n points with triangular convex hull that maximizes the number of halving edges. Moreover, we provide a simpler proof of the following result from [13]: any set of points in the plane in general position has at least 3 j+2 2 � (� j)-edges. This bound is