On halving line arrangements (Q1850013)

Given a set of \(n\) points \((n\) even) in general position in the plane, a halving line is a line going through two of the points and cutting the remaining points in half. Let \(h(n)\) denote the maximum number of halving lines that can be realized by a planar set of \(n\) points. This problem naturally generalizes to pseudoconfigurations, and let \(h'(n)\) denote the maximum number of halving pseudolines over all pseudoconfigurations of size \(n\). The authors prove that \(h'(12)=18\) and that the pseudoconfiguration on 12 points with the largest number of halving pseudolines is unique up to isomorphism and realizable (implying \(h(12)=18).\) In the article, the pseudoconfigurations are described via the counterclockwise systems (CC-systems which are equivalent to rank 3 oriented matroids) defined by D. Knuth. They give several structural results that substantially reduce the computational effort needed to obtain the exact value of \(h'(n)\) for larger \(n\). Using these techniques, they enumerate all topologically distinct, simple arrangements of 10 pseudolines with a marked cell. They also prove that \(h(14)=22\) using certain properties of degree sequences of halving edges graphs (which are the graphs on the points where two points are adjacent if they define a halving line).