Online Hitting Sets for Disks of Bounded Radii
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917043592232960 |
|---|---|
| author | De, Minati Singh, Satyam Tóth, Csaba D. |
| author_facet | De, Minati Singh, Satyam Tóth, Csaba D. |
| contents | We present algorithms for the online minimum hitting set problem in geometric range spaces: given a set $P$ of $n$ points in the plane and a sequence of geometric objects that arrive one-by-one, we need to maintain a hitting set at all times by making irrevocable decisions. For disks of radii in the interval $[1,M]$, we present an $O(\log M \log n)$-competitive algorithm. This result generalizes from disks to positive homothets of any convex body in the plane with scaling factors in the interval $[1,M]$. As a main technical tool, we reduce the problem to the online hitting set problem for a finite subset of integer points and geometric objects with the lowest point property, introduced in this paper, which behave similarly to bottomless rectangles. Specifically, for a given $N>1$, we present an $O(\log N)$-competitive algorithm for the variant where $P$ is a subset of an $N\times N$ section of the integer lattice, and the geometric objects have the lowest point property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04646 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Hitting Sets for Disks of Bounded Radii De, Minati Singh, Satyam Tóth, Csaba D. Computational Geometry We present algorithms for the online minimum hitting set problem in geometric range spaces: given a set $P$ of $n$ points in the plane and a sequence of geometric objects that arrive one-by-one, we need to maintain a hitting set at all times by making irrevocable decisions. For disks of radii in the interval $[1,M]$, we present an $O(\log M \log n)$-competitive algorithm. This result generalizes from disks to positive homothets of any convex body in the plane with scaling factors in the interval $[1,M]$. As a main technical tool, we reduce the problem to the online hitting set problem for a finite subset of integer points and geometric objects with the lowest point property, introduced in this paper, which behave similarly to bottomless rectangles. Specifically, for a given $N>1$, we present an $O(\log N)$-competitive algorithm for the variant where $P$ is a subset of an $N\times N$ section of the integer lattice, and the geometric objects have the lowest point property. |
| title | Online Hitting Sets for Disks of Bounded Radii |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2412.04646 |