2023/03/21 by Minati De, Satyam Singh, De, Minati +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2303.11779
openalex publication_date 2023/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the online hitting set problem for the range space Σ=(\cal X,\cal R), where the point set \cal X is known beforehand, but the set \cal R of geometric objects is not known in advance. Here, objects from \cal R arrive one by one. The objective of the problem is to maintain a hitting set of the minimum cardinality by taking irrevocable decisions. In this paper, we consider the problem when objects are unit balls or unit hypercubes in ℝd, and the points from ℤd are used for hitting them. First, we address the case when objects are unit intervals in ℝ and present an optimal deterministic algorithm with a competitive ratio of~2. Then, we consider the case when objects are unit balls. For hitting unit balls in ℝ2 and ℝ3, we present 4 and 14-competitive deterministic algorithms, respectively. On the other hand, for hitting unit balls in ℝd, we propose an O(d4)-competitive deterministic algorithm, and we demonstrate that, for d<4, the competitive ratio of any deterministic algorithm is at least d+1. In the end, we explore the case where objects are unit hypercubes. For hitting unit hypercubes in ℝ2 and ℝ3, we obtain 4 and 8-competitive deterministic algorithms, respectively. For hitting unit hypercubes in ℝd (d≥ 3), we present an O(d2)-competitive randomized algorithm. Furthermore, we prove that the competitive ratio of any deterministic algorithm for the problem is at least d+1 for any d∈ℕ.