×

On a problem about covering lines by squares. (English) Zbl 0691.52011

Let S be a square of side length \(n\in {\mathbb{N}}\), and let \({\mathcal S}=\{S_ 1,...,S_ t\}\) be a collection of unit squares contained in S and with sides parallel to those of S. \({\mathcal S}\) is called a line cover if every line intersecting S also intersects some \(S_ i\in {\mathcal S}\). Let \(\tau '(n)\) denote the minimum of t such that there is a line cover \({\mathcal S}\) of cardinality t. It is proved that \(\tau '(n)=4n/3+O(1).\) Some related questions are discussed.
Reviewer: A.Florian

MSC:

52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] I. Bárány and Z. Füredi, Covering all secants of a square,Proceedings of the Colloquia Mathematica Societatis János Bolyai, Siofok, Hungary, 1985 (in honor of L. Fejes Tóth), to appear. · Zbl 0629.52011
[2] L. Fejes Tóth, Remarks on a dual of Tarski’s plank problem,Mat. Lapok25 (1974), 13-20. · Zbl 0359.52010
[3] W. O. Moser and J. Pach, Research Problems in Discrete Geometry, Problem 84, Montréal 1985, mimeographed. · Zbl 1086.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.