Geometric hitting set for segments of few orientations

DOI10.1007/s00224-016-9744-7zbMath1384.68021arXiv1603.06077MaRDI 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

zbMATH Keywords

approximation algorithms; set cover; hitting set

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Related Items

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