# New Lower Bound and Algorithms for Online Geometric Hitting Set Problem

arXiv: https://arxiv.org/abs/2409.11166 · HTML: https://mlsanity.com/paper/2409.11166/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2024.

## Built on by (most cited first, 1 of 1)

- [Online Epsilon Net and Piercing Set for Geometric Concepts](https://mlsanity.com/paper/2410.07059/) (2024)

## Abstract (arXiv)

The hitting set problem is one of the fundamental problems in combinatorial optimization and is well-studied in offline setup. We consider the online hitting set problem, where only the set of points is known in advance, and objects are introduced one by one. Our objective is to maintain a minimum-sized hitting set by making irrevocable decisions. Here, we present the study of two variants of the online hitting set problem depending on the point set. In the first variant, we consider the point set to be the entire mathbbZd, while in the second variant, we consider the point set to be a finite subset of ℝ2. If you use points in mathbbZd to hit homothetic hypercubes in ℝd with side lengths in [1,M], we show that the competitive ratio of any algorithm is Omega(dlog M), whether it is deterministic or random. This improves the recently known deterministic lower bound of Omega(log M) by a factor of d. Then, we present an almost tight randomized algorithm with a competitive ratio O(d2log M) that significantly improves the best-known competitive ratio of 25dlog M. Next, we propose a simple deterministic lfloorfrac2α+2rfloord(lfloorlog2Mrfloor+1) competitive algorithm to hit similarly sized α-fat objects in ℝd having diameters in the range [1, M] using points in mathbbZd. This improves the current best-known upper bound by a factor of at least 5d. Finally, we consider the hitting set problem when the point set consists of n points in ℝ2, and the objects are homothetic regular k-gons having diameter in the range [1, M]. We present an O(log nlog M) competitive randomized algorithm for that. Whereas no result was known even for squares. In particular, our results answer some of the open questions raised by Khan et al. (SoCG'23) and Alefkhani et al. (WAOA'23).