Covering grids with multiplicity

Anurag Bishnoi; Simona Boyadzhiyska; Shagnik Das; Yvonne den Bakker

doi:10.5070/C63362787

Covering grids with multiplicity

Anurag Bishnoi, Simona Boyadzhiyska, Shagnik Das, Yvonne den Bakker

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

71 Downloads (Pure)

Abstract

Given a finite grid in R², 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.

Original language	English
Article number	4
Number of pages	22
Journal	Combinatorial Theory
Volume	3
Issue number	3
DOIs	https://doi.org/10.5070/C63362787
Publication status	Published - 2023

Funding

∗This research was done when the author was affiliated with the Institut für Mathematik, Freie Universität Berlin, 14195 Berlin, Germany, and was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689, BMS Stipend) and Graduiertenkolleg “Facets of Complexity” (GRK 2434). †Research supported by Taiwan NSTC grant 111-2115-M-002-009-MY2.

Keywords

Alon–Füredi Theorem
combinatorial geometry
Grid covering
linear programming

Access to Document

10.5070/C63362787

eScholarship UC item 7p97h8mnFinal published version, 578 KBLicence: CC BY

Cite this

@article{504cbfaadffb4eb3ad9c16d3a641f791,

title = "Covering grids with multiplicity",

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.",

keywords = "Alon–F{\"u}redi Theorem, combinatorial geometry, Grid covering, linear programming",

author = "Anurag Bishnoi and Simona Boyadzhiyska and Shagnik Das and {den Bakker}, Yvonne",

year = "2023",

doi = "10.5070/C63362787",

language = "English",

volume = "3",

journal = "Combinatorial Theory",

issn = "2766-1334",

publisher = "eScholarship University of California",

number = "3",

}

TY - JOUR

T1 - Covering grids with multiplicity

AU - Bishnoi, Anurag

AU - Boyadzhiyska, Simona

AU - Das, Shagnik

AU - den Bakker, Yvonne

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - Alon–Füredi Theorem

KW - combinatorial geometry

KW - Grid covering

KW - linear programming

UR - http://www.scopus.com/inward/record.url?scp=85180672266&partnerID=8YFLogxK

U2 - 10.5070/C63362787

DO - 10.5070/C63362787

M3 - Article

AN - SCOPUS:85180672266

SN - 2766-1334

VL - 3

JO - Combinatorial Theory

JF - Combinatorial Theory

IS - 3

M1 - 4

ER -

Covering grids with multiplicity

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this