Improved results on geometric hitting set problems

DOI10.1007/s00454-010-9285-9zbMath1207.68420MaRDI QIDQ603882

Publication date: 8 November 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-010-9285-9

zbMATH Keywords

local search; transversals; approximation algorithms; greedy algorithms; epsilon nets; hitting sets

Mathematics Subject Classification ID

52B55: Computational aspects related to convexity

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

52C15: Packing and covering in (2) dimensions (aspects of discrete geometry)

68W25: Approximation algorithms

Related Items

Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Geometric Packing under Nonuniform Constraints, Constant-Factor Approximation for TSP with Disks, Discrete unit square cover problem, Unnamed Item, Unnamed Item, Hitting and Piercing Rectangles Induced by a Point Set, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames, Planar Support for Non-piercing Regions and Applications, On Geometric Set Cover for Orthants, On Partial Covering For Geometric Set Systems, Capacitated Covering Problems in Geometric Spaces, ON THE DISCRETE UNIT DISK COVER PROBLEM, Unnamed Item, Unnamed Item, Unnamed Item, Covering segments with unit squares, Minimum membership covering and hitting, A constant-factor approximation algorithm for red-blue set cover with unit disks, Capacitated discrete unit disk cover, Covering and packing of rectilinear subdivision, Line segment disk cover, A constant-factor approximation algorithm for red-blue set cover with unit disks, Online unit covering in Euclidean space, Local search strikes again: PTAS for variants of geometric covering and packing, Approximability of covering cells with line segments, Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model, Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions., Improved and generalized algorithms for burning a planar point set, On the geometric priority set cover problem, Improved bounds for metric capacitated covering problems, Complexity and approximation for discriminating and identifying code problems in geometric setups, Exact algorithms and hardness results for geometric red-blue hitting set problem, Geometric dominating-set and set-cover via local-search, Geometric stabbing via threshold rounding and factor revealing LPs, Geometric hitting set for line-constrained disks, Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), Discriminating Codes in Geometric Setups, Tighter estimates for \(\epsilon\)-nets for disks, Following a curve with the discrete Fréchet distance, Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions, Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve, Exact algorithms and APX-hardness results for geometric packing and covering problems, Covering moving points with anchored disks, Unit disk cover problem in 2D, PTAS for minimum \(k\)-path vertex cover in ball graph, Limits of local search: quality and efficiency, The within-strip discrete unit disk cover problem, Improved results on geometric hitting set problems, On pseudo-disk hypergraphs, Minimum ply covering of points with disks and squares, On the approximability of covering points by lines and related problems, Approximability and hardness of geometric hitting set with axis-parallel rectangles, Location, pricing and the problem of Apollonius, PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs, Practical and efficient algorithms for the geometric hitting set problem, Geometric hitting set for segments of few orientations, Packing and covering with non-piercing regions, An exact algorithm for a class of geometric set-cover problems, A primal-dual algorithm for the minimum power partial cover problem, A tight analysis of geometric local search, On the geometric set multicover problem, Existence of planar support for geometric hypergraphs using elementary techniques, Capacitated covering problems in geometric spaces, Local search is a PTAS for feedback vertex set in minor-free graphs, Approximation algorithms for geometric conflict free covering problems, Constructing planar support for non-piercing regions, On the geometric red-blue set cover problem, Near-linear algorithms for geometric hitting sets and set covers, On interval and circular-arc covering problems, Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, Geometric red-blue set cover for unit squares and related problems, Simple PTAS's for families of graphs excluding a minor, Packing and covering with balls on Busemann surfaces, Minimum power partial multi-cover on a line, Discretely Following a Curve, AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS, APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS, On the Discrete Unit Disk Cover Problem, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Geometric Hitting Sets for Disks: Theory and Practice, Minimum Dominating Set Problem for Unit Disks Revisited

Cites Work