首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On a problem about covering lines by squares
Authors:Walter Kern  Alfred Wanka
Institution:(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 isin Nopf and letS = {S 1, ...,S t} 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 someS i isinS. Lettau(n) denote the minimum cardinality of a line cover, and lettauprime(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 thattau(n)=2n+O(1) and by Bárány and Füredi thattauprime(n)=3/2n+O(1). We will prove that, instead,tauprime(n)=4/3n+O(1) and, as to Fejes Tóth's conjecture, we will exhibit a ldquononintegerrdquo solution to a related LP-relaxation, which has size equal to 3/2n+O(1).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号