English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the geometric hitting set problem in the online setup for therange space $\Sigma=({\cal P},{\cal S})$, where the set $\P\subset\mathbb{R}^2$is a collection of $n$ points and the set $\cal S$ is a family of geometricobjects in $\mathbb{R}^2$. In the online setting, the geometric objects arriveone by one. Upon the arrival of an object, an online algorithm must maintain avalid hitting set by making an irreversible decision, i.e., once a point isadded 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 ofthe minimum cardinality. Even and Smorodinsky (Discret. Appl. Math., 2014)considered an online model (Model-I) in which the range space $\Sigma$ is knownin advance, but the order of arrival of the input objects in $\cal S$ isunknown. They proposed online algorithms having optimal competitive ratios of$\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 longtime. This paper considers an online model (Model-II) in which the entire rangespace $\Sigma$ is not known in advance. We only know the set $\cal P$ but notthe set $\cal S$ in advance. Note that any algorithm for Model-II will alsowork for Model-I, but not vice-versa. In Model-II, we obtain an optimalcompetitive ratio of $\Theta(\log(n))$ for unit disks and regular $k$-gon with$k\geq 4$ in $\mathbb{R}^2$. All the above-mentioned results also hold for theequivalent geometric set cover problem in Model-II.

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