Online Geometric Hitting Set and Set Cover Beyond Unit Balls in ${\mathbb{R}}^2$

We investigate the geometric hitting set problem in the online setup for the range space $\mathrm{\Sigma }=(\mathcal{P},\mathcal{S})$, where the set $\mathrm{\P }\subset {\mathbb{R}}^2$ is a collection of $n$ points and the set $\mathcal{S}$ is a family of geometric objects in ${\mathbb{R}}^2$. In the online setting, the geometric objects arrive one by one. Upon the arrival of an object, an online algorithm must maintain a valid hitting set by making an irreversible decision, i.e., once a point is added to the hitting set by the algorithm, it can not be deleted in the future. The objective of the geometric hitting set problem is to find a hitting set of the minimum cardinality. Even and Smorodinsky (Discret. Appl. Math., 2014) considered an online model (Model-I) in which the range space $\mathrm{\Sigma }$ is known in advance, but the order of arrival of the input objects in $\mathcal{S}$ is unknown. They proposed online algorithms having optimal competitive ratios of $\mathrm{\Theta }(\log n)$ for intervals, half-planes and unit disks in ${\mathbb{R}}^2$. Whether such an algorithm exists for unit squares remained open for a long time. This paper considers an online model (Model-II) in which the entire range space $\mathrm{\Sigma }$ is not known in advance. We only know the set $\mathcal{P}$ but not the set $\mathcal{S}$ in advance. Note that any algorithm for Model-II will also work for Model-I, but not vice-versa. In Model-II, we obtain an optimal competitive ratio of $\mathrm{\Theta }(\log (n))$ for unit disks and regular $k$-gon with $k\ge 4$ in ${\mathbb{R}}^2$. All the above-mentioned results also hold for the equivalent geometric set cover problem in Model-II.