Publ. I.R.M.A. Strasbourg, 1987, 340/S–15 Actes 15^{e} Séminaire Lotharingien, p. 129

ON A PROBLEM ABOUT COVERING

LINES BY SQUARES

BY

WALTER KERN and ALFRED WANKA

ABSTRACT. — Let S be the square [0, n]^{2} of side length n ∈ N and let S = {S_{1}, …, S_{t}} be a set of unit squares lying inside S, whose sides are parallel to those of S. The set S is called a line cover, if every line intersecting S also intersetcs some S_{i} ∈ 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 of S. It has been conjectured by L.F. T^{}ÓTH that τ(n) = 2n+0(1) and I. B^{}ÁR^{}ÁNYI and Z. F^{}ÜREDI that τ(n) = \frac{3}{2}n+0(1). We will prove instead, τ′(n) = \frac{4}{3} + 0(1), and as to T^{}ÓTH’s conjecture, we will exhibit a “non integer” solution to a related LP-relaxation, which has size equal to \frac{3}{2} + 0(1).

REFERENCES

FEJES T^{}ÓTH (L.). — Remarks on a dual of Tarski’s plank problem, Mat. Lapok, vol. 25, 1974, p. 13–20.

MOSER (W.O.) and PACH (J.). — Research Problems in Discrete Geometry, Problem 84, Montréal, 1984, mimeographed.

B^{}ÁR^{}ÁNYI (L.) and F^{}ÜREDI (Z.). — Covering all secants of a square, Rutcor Research Report 3–36, Rutgers Univ., New Brunswick, N.J., March 1986.

Walter KERN u. Alfred WANKA, Mathematisches Institut, der Universität zu Köln, Weyertal 86–90, D-5000 Köln.