Covering grids with multiplicity
A. Bishnoi (TU Delft - Discrete Mathematics and Optimization)
Simona Boyadzhiyska (University of Birmingham)
Shagnik Das (National Taiwan University)
Yvonne den Bakker (Student TU Delft)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Given a finite grid in R2, 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, …, n − 1} × {0, …, 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.
help_outline