2024/09/17 by Minati De, De, Minati, Ratnadip Mandal +3 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2409.11166
openalex publication_date 2024/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℤd, while in the second variant, we consider the point set to be a finite subset of ℝ2. If you use points in ℤd to hit homothetic hypercubes in ℝd with side lengths in [1,M], we show that the competitive ratio of any algorithm is Ω(dlog M), whether it is deterministic or random. This improves the recently known deterministic lower bound of Ω(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 \lfloor\frac2α+2\rfloord(\lfloorlog2M\rfloor+1) competitive algorithm to hit similarly sized α-fat objects in ℝd having diameters in the range [1, M] using points in ℤd. 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).