Geodesic
On a Problem about Covering Lines by Squares
Séminaire lotharingien de combinatoire, Tome 15 (1986)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

Let S be the square [0,n]x[0,n] of side length n and let T={S(1),...,S(t)} be a set of unit squares lying inside S, whose sides are parallel to those of S. The set T is called a line cover, if every line intersecting S also intersects some S in T. Let t(n) denote the minimum cardinality of a line cover, and let t'(n) be defined in the same way, except that we restrict our attention to lines which are parallel to either one of the axes or one of the diagonals of S. It has been conjectured by Toth that t(n)=2n+0(1) and Baranyi and Füredi that t(n)=(3/2)n+0(1). We will prove instead, t'(n)=(4/3)+0(1), and as to Toth's conjecture, we will exhibit a ``non integer" solution to a related LP-relaxation, which has size equal to (3/2)+0(1). 

@article{SLC_1986_15_a1,
     author = {Walter Kern and Alfred Wanka},
     title = {On a {Problem} about {Covering} {Lines} by {Squares}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {15},
     year = {1986},
     url = {http://geodesic.mathdoc.fr/item/SLC_1986_15_a1/}
}
TY  - JOUR
AU  - Walter Kern
AU  - Alfred Wanka
TI  - On a Problem about Covering Lines by Squares
JO  - Séminaire lotharingien de combinatoire
PY  - 1986
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1986_15_a1/
ID  - SLC_1986_15_a1
ER  - 
%0 Journal Article
%A Walter Kern
%A Alfred Wanka
%T On a Problem about Covering Lines by Squares
%J Séminaire lotharingien de combinatoire
%D 1986
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1986_15_a1/
%F SLC_1986_15_a1
Walter Kern; Alfred Wanka. On a Problem about Covering Lines by Squares. Séminaire lotharingien de combinatoire, Tome 15 (1986). http://geodesic.mathdoc.fr/item/SLC_1986_15_a1/