Online Hitting of Unit Balls and Hypercubes in $\mathbb{R}^d$ using Points from $\mathbb{Z}^d$
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908720452075520 |
|---|---|
| author | De, Minati Singh, Satyam |
| author_facet | De, Minati Singh, Satyam |
| contents | 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 $\mathbb{R}^d$, and the points from $\mathbb{Z}^d$ are used for hitting them. First, we address the case when objects are unit intervals in $\mathbb{R}$ 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 $\mathbb{R}^2$ and $\mathbb{R}^3$, we present $4$ and $14$-competitive deterministic algorithms, respectively. On the other hand, for hitting unit balls in $\mathbb{R}^d$, we propose an $O(d^4)$-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 $\mathbb{R}^2$ and $\mathbb{R}^3$, we obtain $4$ and $8$-competitive deterministic algorithms, respectively. For hitting unit hypercubes in $\mathbb{R}^d$ ($d\geq 3$), we present an $O(d^2)$-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\in\mathbb{N}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_11779 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Online Hitting of Unit Balls and Hypercubes in $\mathbb{R}^d$ using Points from $\mathbb{Z}^d$ De, Minati Singh, Satyam Computational Geometry 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 $\mathbb{R}^d$, and the points from $\mathbb{Z}^d$ are used for hitting them. First, we address the case when objects are unit intervals in $\mathbb{R}$ 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 $\mathbb{R}^2$ and $\mathbb{R}^3$, we present $4$ and $14$-competitive deterministic algorithms, respectively. On the other hand, for hitting unit balls in $\mathbb{R}^d$, we propose an $O(d^4)$-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 $\mathbb{R}^2$ and $\mathbb{R}^3$, we obtain $4$ and $8$-competitive deterministic algorithms, respectively. For hitting unit hypercubes in $\mathbb{R}^d$ ($d\geq 3$), we present an $O(d^2)$-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\in\mathbb{N}$. |
| title | Online Hitting of Unit Balls and Hypercubes in $\mathbb{R}^d$ using Points from $\mathbb{Z}^d$ |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2303.11779 |