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 ℝ has a competitive ratio of at least 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 ℝd. For homothetic hypercubes in ℝd with side length in the range [1,k], we propose a deterministic algorithm having a competitive ratio of at most~3dlceillog2 krceil+2d. In the end, we show deterministic lower bounds of the competitive ratio for similarly sized α-fat objects in ℝ2 and homothetic hypercubes in ℝ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 ℝd.