On a problem about covering lines by squares |
| |
Authors: | Walter Kern Alfred Wanka |
| |
Affiliation: | (1) Mathematisches Institut der Universität zu Köln, Weyertal 86-90, D-5000 Köln 41, Germany |
| |
Abstract: | LetS be the square [0,n]2 of side lengthn and letS = {S1, ...,St} be a set of unit squares lying insideS, whose sides are parallel to those ofS.S is called a line cover, if every line intersectingS also intersects someSi S. Let(n) denote the minimum cardinality of a line cover, and let(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 ofS. It has been conjectured by Fejes Tóth that(n)=2n+O(1) and by Bárány and Füredi that(n)=3/2n+O(1). We will prove that, instead,(n)=4/3n+O(1) and, as to Fejes Tóth's conjecture, we will exhibit a noninteger solution to a related LP-relaxation, which has size equal to 3/2n+O(1). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|