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, Jan 24 2008
From Rob Pratt, Jul 22 2015: (Start)
Because each line covers at most n-1 unchosen points, we have (n-1) * binomial(t,2) >= (n-1)^2 - t, yielding a lower bound of a(n) >= ceiling((n - 3 + sqrt(8n^3 + 9n^2 - 14n + 1))/(2*(n-1))).
Can be formulated as an integer linear programming problem as follows. Let binary variable x[i,j] = 1 if lattice point (i,j) is chosen, and 0 otherwise. Let binary variable y[k] = 1 if line k is chosen, and 0 otherwise. The objective is to minimize sum x[i,j]. Let L[k] denote the set of lattice points on line k. The covering constraint for lattice point (i,j) is sum {k: (i,j) in L[k]} y[k] >= 1. To enforce the rule that y[k] = 1 implies sum {(i,j) in L[k]} x[i,j] >= 2, impose the linear constraint sum {(i,j) in L[k]} x[i,j] >= 2 * y[k]. (End)
LINKS
N. Alon, Economical 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 Defined With a Minimum Sublattice, arXiv:0811.2434 [math.CO], 2008.
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
KEYWORD
nonn,hard,more
AUTHOR
W. Edwin Clark, Mar 15 2006
EXTENSIONS
a(7)-a(9) from Rob Pratt, Jul 22 2015
STATUS
approved