Online Geometric Covering and Piercing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909239926063104 |
|---|---|
| author | De, Minati Jain, Saksham Kallepalli, Sarat Varma Singh, Satyam |
| author_facet | De, Minati Jain, Saksham Kallepalli, Sarat Varma Singh, Satyam |
| contents | 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}$ has a competitive ratio of at least $Ω(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$. For homothetic hypercubes in $\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$. In the end, we show deterministic lower bounds of the competitive ratio for similarly sized $α$-fat objects in $\mathbb{R}^2$ and homothetic hypercubes in $\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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02445 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Online Geometric Covering and Piercing De, Minati Jain, Saksham Kallepalli, Sarat Varma Singh, Satyam Computational Geometry 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}$ has a competitive ratio of at least $Ω(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$. For homothetic hypercubes in $\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$. In the end, we show deterministic lower bounds of the competitive ratio for similarly sized $α$-fat objects in $\mathbb{R}^2$ and homothetic hypercubes in $\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$. |
| title | Online Geometric Covering and Piercing |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2305.02445 |