Approximability of covering cells with line segments
DOI10.1016/j.tcs.2019.05.004zbMath1425.68428arXiv1809.09979OpenAlexW3022883705WikidataQ127849503 ScholiaQ127849503MaRDI QIDQ5919568
Saeed Mehrabi, Anil Maheshwari, Luís Fernando Schultz Xavier da Silveira, Paz Carmi, Xavier da Silveira, Luís Fernando Schultz
Publication date: 13 August 2019
Published in: Theoretical Computer Science, Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.09979
approximation algorithmsfixed-parameter tractabilitygeometric covering\(\mathsf{APX}\)-hardness\(\mathsf{PTAS}\)line segment covering
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Approximation algorithms for a geometric set cover problem
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- Improved approximation algorithms for geometric set cover
- Optimization, approximation, and complexity classes
- Approximating domination on intersection graphs of paths on a grid
- Almost optimal set covers in finite VC-dimension
- Packing and covering with non-piercing regions
- Geometric red-blue set cover for unit squares and related problems
- Line segment covering of cells in arrangements
- Covering things with things
- Weighted geometric set cover via quasi-uniform sampling
- A threshold of ln n for approximating set cover
- Unique Covering Problems with Geometric Sets
- Approximation Schemes for Covering and Packing
- Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
- Planar Support for Non-piercing Regions and Applications
- Covering segments with unit squares
- Approximability of covering cells with line segments
