TY - JOUR
T1 - Covering grids with multiplicity
AU - Bishnoi, Anurag
AU - Boyadzhiyska, Simona
AU - Das, Shagnik
AU - Bakker, Yvonne den
PY - 2023/12/22
Y1 - 2023/12/22
N2 - 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.
AB - 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.
U2 - 10.5070/C63362787
DO - 10.5070/C63362787
M3 - Article
SN - 2766-1334
VL - 3
JO - Combinatorial Theory
JF - Combinatorial Theory
IS - 3
M1 - 4
ER -