Geometric hitting set for segments of few orientations
From MaRDI portal
Publication:1743112
DOI10.1007/s00224-016-9744-7zbMath1384.68021arXiv1603.06077OpenAlexW2950710020MaRDI QIDQ1743112
Kan Huang, Cynthia A. Phillips, Ojas Parekh, Joseph S. B. Mitchell, Sándor P. Fekete
Publication date: 12 April 2018
Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.06077
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Geometric stabbing via threshold rounding and factor revealing LPs, Graphs with equal domination and covering numbers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and lower bounds for stabbing problems
- Approximation algorithms for a geometric set cover problem
- Improved results on geometric hitting set problems
- Guarding a set of line segments in the plane
- A non-linear lower bound for planar epsilon-nets
- Improved approximation algorithms for geometric set cover
- On the approximability of covering points by lines and related problems
- Hitting sets when the VC-dimension is small
- Approximation algorithms for hitting objects with straight lines
- On the complexity of locating linear facilities in the plane
- Almost optimal set covers in finite VC-dimension
- Covering things with things
- Approximability issues of guarding a set of segments
- Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Greedy Heuristic for the Set-Covering Problem
- Tight lower bounds for the size of epsilon-nets
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Algorithms for polytope covering and approximation
- Analytical approach to parallel repetition
- Point Line Cover: The Easy Kernel is Essentially Tight
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems