Sets of points with many halving lines
David Eppstein · 1992
We used a genetic search algorithm to find sets of points with many halving lines. There are sets of 10 points with 13 halving lines, 12 points with 18 halving lines, 14 points with 22 halving lines, 16 points with 27 halving lines, and 18 points with 32 halving lines. We find a construction generalizing the 12 point configuration and show that, for any n =3 2 i , there are configurations of n points with n log 4 (2n/3) = 3(i + 1)2 i-1 halving lines. Figure 1. (a) 4 points, 3 halving lines; (b) 6 points, 6 halving lines. 1 Introduction Counting halving lines is one of the important open problems of combinatorial geometry. A halving line for a set of n points (n even) is a line passing through two of the points, and cutting the remaining set of n - 2 points in half. Given any set S, we define H(S) to be the set of such lines. We are interested in bounding the worst-case size of this set, h(n) = max |S|=n |H(S)|. The best known lower bound gives a construction for sets...