Donald Bren School of Information and Computer Sciences

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.