Covering grids with multiplicity
Abstract
Given a finite grid in \(\mathbb{R}^2\), how many lines are needed to cover all but one point at least \(k\) times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball-Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball-Serra and provide an asymptotic answer for almost all grids. For the standard grid \(\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}\), we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments.
Mathematics Subject Classifications: 05B40, 52C15, 05D40
Keywords: Grid covering, Alon-Füredi Theorem, combinatorial geometry, linear programming