Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 46 min ago
PreprintCC BY-NC-ND 4.0arXiv

On Guarding Line Arrangements

  • Valentin Brimkov
Open at sourcePDFDOICite

Abstract

We study the problem of guarding a set of straight lines in the plane by selecting a minimum-cardinality set of points such that every line contains at least one selected point. This problem is known to be strongly NP-hard \cite{megiddo}. We investigate approximation algorithms for the problem and analyze their performance guarantees under various structural assumptions on the underlying line arrangement. In particular, we present approximation schemes based on set-cover techniques, relaxation methods, and properties of maximal lines. We establish constant-factor bounds on the approximation ratio for several classes of arrangements and derive relationships between the guarding number and the incidence parameters of the arrangement. Connections with Dirac-type incidence results are also explored.

Related

  1. Topological line arrangements with high multiplicities
    Paolo Aceto, Marco Golla
    HALPreprintLicence not statedGeometry & topologyHAL
  2. A generalized Saito criterion, from line arrangements to curves
    Anca Măcinic
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. Line arrangements, bounded cells, and discrepancy
    Imre Bárány
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The opposite of admissibility for local systems on line arrangements
    Robert Harris
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. A generalized Terao Conjecture for line arrangements
    Alexandru Dimca, Piotr Pokora
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{brimkov2026guarding,
  title = {{On Guarding Line Arrangements}},
  author = {Valentin Brimkov},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.02046},
  eprint = {2611.02046},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02046},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - On Guarding Line Arrangements
AU  - Valentin Brimkov
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.02046
UR  - https://arxiv.org/abs/2611.02046
AB  - We study the problem of guarding a set of straight lines in the plane by selecting a minimum-cardinality set of points such that every line contains at least one selected point. This problem is known to be strongly NP-hard \cite{megiddo}. We investigate approximation algorithms for the problem and analyze their performance guarantees under various structural assumptions on the underlying line arrangement. In particular, we present approximation schemes based on set-cover techniques, relaxation methods, and properties of maximal lines. We establish constant-factor bounds on the approximation ratio for several classes of arrangements and derive relationships between the guarding number and the incidence parameters of the arrangement. Connections with Dirac-type incidence results are also explored.
ER  -