Online Geometric Covering and Piercing

We consider the online version of the piercing set problem, where geometric objects arrive one by one, and the online algorithm must maintain a valid piercing set for the already arrived objects by making irrevocable decisions. It is easy to observe that any deterministic algorithm solving this problem for intervals in \(\mathbb {R}\) $\mathbb{R}$ has a competitive ratio of at least \(\Omega (n)\) $\mathrm{\Omega }(n)$ . This paper considers the piercing set problem for similarly sized objects. We propose a deterministic online algorithm for similarly sized fat objects in \(\mathbb {R}^d\) ${\mathbb{R}}^d$ . For homothetic hypercubes in \(\mathbb {R}^d\) ${\mathbb{R}}^d$ with side length in the range [1, k], we propose a deterministic algorithm having a competitive ratio of at most  \(3^d\lceil \log _2 k\rceil +2^d\) $3^d\lceil {log}_{2}k\rceil +2^d$ . In the end, we show deterministic lower bounds of the competitive ratio for similarly sized \(\alpha \) $\alpha$ -fat objects in \(\mathbb {R}^2\) ${\mathbb{R}}^2$ and homothetic hypercubes in \(\mathbb {R}^d\) ${\mathbb{R}}^d$ . Note that piercing translated copies of a convex object is equivalent to the unit covering problem, which is well-studied in the online setup. Surprisingly, no upper bound of the competitive ratio was known for the unit covering problem when the corresponding object is anything other than a ball or a hypercube. Our result yields an upper bound of the competitive ratio for the unit covering problem when the corresponding object is any convex object in \(\mathbb {R}^d\) ${\mathbb{R}}^d$ .