An Improvement of the Lower Bound on the Maximum Number of Halving Lines for Sets in the Plane with an Odd Number of Points

Abstract

In this paper, we give examples that improve the lower bound on the maximum number of halving lines for sets in the plane with 35, 59, 95, and 97 points and, as a consequence, we improve the current best upper bound of the rectilinear crossing number for sets in the plane with 35, 59, 95, and 97 points, provided that a conjecture included in the literature is true. As another consequence, we also improve the lower bound on the maximum number of halving pseudolines for sets in the plane with 35 points. These examples, and the recursive bounds for the maximum number of halving lines for sets with an odd number of points achieved, give a new insight in the study of the rectilinear crossing number problem, one of the most challenging tasks in Discrete Geometry. With respect to this problem, it is conjectured that, for all n multiples of 3, there are 3-symmetric sets of n points for which the rectilinear crossing number is attained.

Keywords

• discrete geometry
• halving lines
• rectilinear crossing number
• optimization