On a problem about covering lines by squares
Kern, Walter and Wanka, Alfred
(1990)
On a problem about covering lines by squares.
Published in:
Discrete & Computational Geometry Vol. 5 (1).
pp. 7782.
Abstract
Let S be the square [0,n]^2 of side length nin {f N} and let {cal S}={ S_1,ldots,S_t} be a set of unit squares lying inside S, whose sides are parallel to those of S. The set cal S is called a line cover, if every line intersecting S also intersects some S_iin {cal S}. Let au (n) denote the minimum cardinality of a line cover, and let au '(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 L.F. Tôth that au (n)=2n+0(1) and I. Barányi and Z. Füredi that au (n)={3over 2}n+0(1). We will prove instead, au '(n)={4over 3}+0(1), and as to Tôth's conjecture, we will exhibit a ''non integerÅœÅœ solution to a related LPrelaxation, which has size equal to {3over 2}+0(1).
Item Type:  Article 

Citations:  4 (Google Scholar)  2 (Web of Science) 
Uncontrolled Keywords:  covering lines by squares distribution of points in a square 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr86031 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  09 Jan 2012 11:51 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/31 