Point Location in Constant Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917558999842816 |
|---|---|
| author | Chaganti, Sairam Han, Yijie |
| author_facet | Chaganti, Sairam Han, Yijie |
| contents | We preprocess the input subdivision with $n$ points on the plane in $O(n\sqrt{\log n})$ time to facilitate point location in constant time. Previously the preprocessing time is $O(n\log n)$ and point location takes $O(\log n)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_02440 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Point Location in Constant Time Chaganti, Sairam Han, Yijie Computational Geometry 68W05, 68W40, F.2.2 We preprocess the input subdivision with $n$ points on the plane in $O(n\sqrt{\log n})$ time to facilitate point location in constant time. Previously the preprocessing time is $O(n\log n)$ and point location takes $O(\log n)$ time. |
| title | Point Location in Constant Time |
| topic | Computational Geometry 68W05, 68W40, F.2.2 |
| url | https://arxiv.org/abs/2401.02440 |