

A076523


Maximal number of halving lines for 2n points in plane.


0



1, 3, 6, 9, 13, 18, 22, 27, 33, 38, 44, 51, 57
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Let S be a set of n points in the plane. A halving line is a line through two points in S that splits the remaining points into two equalsized subsets. How many halving lines can S have?
The values n = 8, 9, 10, 11, 12 and 13 were obtained by Abrego et al. The same values hold also for the maximum number of pseudohalving lines in a generalized configuration of 2n points. The next unknown value, n = 14 (i.e. the maximum number of halving lines among 28 points), is either 63 or 64.  Bernardo M Abrego (bernardo.abrego(AT)csun.edu), May 05 2008


LINKS

Table of n, a(n) for n=1..13.
B. M. Abrego, S. FernandezMerchant, J. LeaĆ±os and G. Salazar, The maximum number of halving lines and the rectilinear crossing number of K_n for n <= 27, Electronic Notes in Discrete Mathematics, 30 (2008), 261266.
A. Beygelzimer and S. Radziszowski, On halving line arrangements, Discrete Math., 257 (2002), 267283.
Jeff Erickson, Halving lines and ksets
Tanya Khovanova and Dai Yang, Halving Lines and Their Underlying Graphs, arXiv:1210.4959 [math.CO], 2012.
Tanya Khovanova, Dai Yang, Connected Components of Underlying Graphs of Halving Lines, arXiv:1304.5658 [math.CO], 2013.
Tanya Khovanova, Dai Yang, Fission of Halving Edges Graphs, arXiv:1310.3510 [math.CO], 2013.
Geza Toth, Point sets with many ksets, in Proceedings of the 16th Annual ACM Symposium on Computational Geometry, 2000, pp. 3742.


CROSSREFS

Sequence in context: A004131 A171514 A032782 * A282720 A129403 A154287
Adjacent sequences: A076520 A076521 A076522 * A076524 A076525 A076526


KEYWORD

nonn,more


AUTHOR

N. J. A. Sloane, Oct 18 2002


EXTENSIONS

More terms from Bernardo M Abrego (bernardo.abrego(AT)csun.edu), May 05 2008


STATUS

approved



