Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
From MaRDI portal
Publication:5390595
DOI10.1137/090762968zbMath1209.68624OpenAlexW2119142868MaRDI QIDQ5390595
Esther Ezra, Boris Aronov, Micha Sharir
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090762968
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20) Combinatorial complexity of geometric structures (52C45)
Related Items (max. 100)
Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ A Characterization of Visibility Graphs for Pseudo-polygons ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ A new upper bound for the VC-dimension of visibility regions ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ Small strong epsilon nets ⋮ Capacitated covering problems in geometric spaces ⋮ Geometric Packing under Nonuniform Constraints ⋮ The class cover problem with boxes ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Constrained hitting set problem with intervals ⋮ Geometric hitting set for segments of few orientations ⋮ On the number of points in general position in the plane ⋮ Piercing axis-parallel boxes ⋮ \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets ⋮ Exact and approximation algorithms for geometric and capacitated set cover problems ⋮ On Wegner's inequality for axis-parallel rectangles ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Hitting and Piercing Rectangles Induced by a Point Set ⋮ Piercing all translates of a set of axis-parallel rectangles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Computing coverage kernels under restricted settings ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ On Geometric Set Cover for Orthants ⋮ An efficient container lemma ⋮ When are epsilon-nets small? ⋮ Subsampling in Smoothed Range Spaces ⋮ On Partial Covering For Geometric Set Systems ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Small candidate set for translational pattern search ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity ⋮ Unnamed Item ⋮ Piercing all translates of a set of axis-parallel rectangles
This page was built for publication: Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
