Improved results on geometric hitting set problems

DOI10.1007/s00454-010-9285-9zbMath1207.68420OpenAlexW2018541722MaRDI 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

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25)

Related Items (88)

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

Cites Work

This page was built for publication: Improved results on geometric hitting set problems