Cover Image

New Lower Bound and Algorithms for Online Geometric Hitting Set Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	De, Minati, Mandal, Ratnadip, Singh, Satyam
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Geometric Hitting Set and Set Cover Beyond Unit Balls in $\mathbb{R}^2$
by: De, Minati, et al.
Published: (2023)

Online Hitting Sets for Disks of Bounded Radii
by: De, Minati, et al.
Published: (2024)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

Online Class Cover Problem
by: De, Minati, et al.
Published: (2023)

Online Hitting Set for Axis-Aligned Squares
by: De, Minati, et al.
Published: (2025)

Online Hitting of Unit Balls and Hypercubes in $\mathbb{R}^d$ using Points from $\mathbb{Z}^d$
by: De, Minati, et al.
Published: (2023)

Online Geometric Covering and Piercing
by: De, Minati, et al.
Published: (2023)

Online Epsilon Net and Piercing Set for Geometric Concepts
by: Bhore, Sujoy, et al.
Published: (2024)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
by: Liu, Gang, et al.
Published: (2024)

An Optimal Algorithm for Half-plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

On Stable Approximation Algorithms for Geometric Coverage Problems
by: de Berg, Mark, et al.
Published: (2024)

Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
by: Abrahamsen, Mikkel, et al.
Published: (2025)

Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds
by: Chung, Jaehoon
Published: (2026)

Minimum-Weight Half-Plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Geometric Bipartite Matching Based Exact Algorithms for Server Problems
by: Raghvendra, Sharath, et al.
Published: (2025)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Lower Bounds from Succinct Hitting Sets
by: Chatterjee, Prerona, et al.
Published: (2023)

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults
by: Biniaz, Ahmad, et al.
Published: (2024)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Minimum Membership Geometric Set Cover in the Continuous Setting
by: Govindarajan, Sathish, et al.
Published: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2025)

Improved Lower Bound on the Number of Pseudoline Arrangements
by: Dallant, Justin
Published: (2024)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
by: Spalding-Jamieson, Jack, et al.
Published: (2025)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

Ordered Front-to-back Any-Hit Traversal in RTX
by: Wald, Ingo
Published: (2026)

Some Lower Bounds on the Reach of an Algebraic Variety
by: La Valle, Chris, et al.
Published: (2024)

Asymmetric Separation Problem for Bichromatic Point Set
by: Maji, Sukanya, et al.
Published: (2024)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
by: Gao, Jie, et al.
Published: (2025)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
by: Gribanov, Dmitry, et al.
Published: (2026)

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
by: Bhore, Sujoy, et al.
Published: (2025)

Subset Selection Problems in Planar Point Sets
by: Balogh, József, et al.
Published: (2024)

Witness Set: A Visibility Problem in $NP\cap XP$
by: Jana, Satyabrata, et al.
Published: (2026)

Hitting Axis-Parallel Segments with Weighted Points
by: Raman, Rajiv, et al.
Published: (2026)

Optimal Algorithm for the Planar Two-Center Problem
by: Cho, Kyungjin, et al.
Published: (2020)

Dominating Set, Independent Set, Discrete $k$-Center, Dispersion, and Related Problems for Planar Points in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2024)