|
| |
|
|
A116446
|
|
Let Sq(n) denote the square grid consisting of all lattice points (x,y) such that x,y are in {0,1,...,n}. a(n) is the minimum number t such that there are t of the (n+1)^2 lattice points in Sq(n) so that the binomial(t,2) lines that they determine cover all points in Sq(n).
|
|
0
| | |
|
|
|
OFFSET
| 1,1
|
|
|
COMMENTS
| No exact values are given in the paper by Alon, however one will find there upper and lower bounds involving unknown constants for the d-dimensional generalization of this sequence.
The upper bound a(n)<=2(n+1) is found by choosing n+1 lines parallel to one of the square's edges, fixed by 2(n+1) points on 2 opposite edges of the grid. Another upper bound a(n)<=3+A018805(floor[(n+1)/2]) is obtained by placing one point at the grid center (n even) or at one of the 4 grid points closest to the center (n odd), then letting 2+A018805(...) lines intersect there. - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jan 24 2008
|
|
|
LINKS
| N. Alon, Economial coverings of sets of lattice points, Geometric and Functional Analysis 1(3) (1991), pp. 225-230. doi:10.1007/BF01896202
R. J. Mathar, Finite Square Lattice Vertex Cover by a Baseline Set..., arXiv:0811.2434 [math.CO].
|
|
|
EXAMPLE
| a(1) = 4 since the square Sq(1) = {(0,0),(1,0),(0,1),(1,1)} cannot be covered by lines determined by 3 points, but is covered by the lines determined by all 4 points in Sq(1).
|
|
|
CROSSREFS
| Sequence in context: A160401 A114742 A098013 * A073229 A102126 A097918
Adjacent sequences: A116443 A116444 A116445 * A116447 A116448 A116449
|
|
|
KEYWORD
| hard,more,nonn
|
|
|
AUTHOR
| W. Edwin Clark (eclark(AT)math.usf.edu), Mar 15 2006
|
| |
|
|
