Metraipolis › archive › dc_9f319f7a08bb

On Guarding Line Arrangements — arXiv:2611.02046

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02046
License (as archived)
CC0-1.0
Archived
2026-11-03T18:50:20.629Z
SHA-256 of the archived text
aa3548afe553a0a601bed32b5244e7f07fa5a82715310daaf1850b525229bc4e
Stable URL of this page
https://metraipolis.com/documento/dc_9f319f7a08bb

How to cite

On Guarding Line Arrangements — arXiv:2611.02046 — arXiv (en), https://arxiv.org/abs/2611.02046 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9f319f7a08bb (Metraipolis archive dc_9f319f7a08bb, sha256 aa3548afe553a0a601bed32b5244e7f07fa5a82715310daaf1850b525229bc4e)
BibTeX
@misc{dc9f319f7a08bb,
  title = {On Guarding Line Arrangements — arXiv:2611.02046},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02046},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9f319f7a08bb; sha256 aa3548afe553a0a601bed32b5244e7f07fa5a82715310daaf1850b525229bc4e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02046. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2611.02046 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:15:38.087Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).