Near-linear algorithms for geometric hitting sets and set covers

DOI10.1007/s00454-019-00099-6zbMath1448.68445OpenAlexW2943969585WikidataQ127907164 ScholiaQ127907164MaRDI QIDQ2291457

Jiangwei Pan, Pankaj K. Agarwal

Publication date: 31 January 2020

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

Full work available at URL: https://doi.org/10.1007/s00454-019-00099-6

zbMATH Keywords

disksgeometric set coverrectanglesmultiplicative weight methodnear-linear algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (5)

On the geometric set multicover problem ⋮ Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\) ⋮ Unnamed Item ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tighter estimates for \(\epsilon\)-nets for disks
• A nearly linear-time PTAS for explicit fractional packing and covering linear programs
• Improved results on geometric hitting set problems
• A non-linear lower bound for planar epsilon-nets
• Improved approximation algorithms for geometric set cover
• \(\epsilon\)-nets and simplex range queries
• Optimal packing and covering in the plane are NP-complete
• Reporting points in halfspaces
• Efficient partition trees
• Adaptive game playing using multiplicative weights
• Quasi-optimal range searching in spaces of finite VC-dimension
• Almost optimal set covers in finite VC-dimension
• A sublinear-time randomized approximation algorithm for matrix games
• Near-linear approximation algorithms for geometric hitting sets
• On the set multicover problem in geometric settings
• Semialgebraic Range Reporting and Emptiness Searching with Applications
• New Lower Bounds for ϵ-nets
• A threshold of ln n for approximating set cover
• New existence proofs ε-nets
• On Approximating the Depth and Related Problems
• Filtering Search: A New Approach to Query-Answering
• Decomposable searching problems I. Static-to-dynamic transformation
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Geometric Set Cover and Hitting Sets for Polytopes in R
• Tight lower bounds for the size of epsilon-nets
• Algorithms for polytope covering and approximation
• Small-size relative ( p ,ε)-approximations for well-behaved range spaces
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Epsilon nets and union complexity
• Approximation algorithms for maximum independent set of pseudo-disks
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• Improved Bounds for the Union of Locally Fat Objects in the Plane

This page was built for publication: Near-linear algorithms for geometric hitting sets and set covers