Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
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_ | 1866911802885931008 |
|---|---|
| author | Chan, Timothy M. Cheng, Pingan Zheng, Da Wei |
| author_facet | Chan, Timothy M. Cheng, Pingan Zheng, Da Wei |
| contents | Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries:
1. Semialgebraic range stabbing. We present a data structure for $n$ semialgebraic ranges in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of ranges containing a query point in $O(n^{1/4+\varepsilon})$ time, for an arbitrarily small constant $\varepsilon>0$.
2. Ray shooting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in $O(n^{1/4+\varepsilon})$ time.
3. Intersection counting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in $O(n^{1/2+\varepsilon})$ time. In particular, this implies an $O(n^{3/2+\varepsilon})$-time algorithm for counting intersections between two sets of $n$ algebraic arcs in 2D. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12303 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane Chan, Timothy M. Cheng, Pingan Zheng, Da Wei Computational Geometry Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1. Semialgebraic range stabbing. We present a data structure for $n$ semialgebraic ranges in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of ranges containing a query point in $O(n^{1/4+\varepsilon})$ time, for an arbitrarily small constant $\varepsilon>0$. 2. Ray shooting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in $O(n^{1/4+\varepsilon})$ time. 3. Intersection counting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in $O(n^{1/2+\varepsilon})$ time. In particular, this implies an $O(n^{3/2+\varepsilon})$-time algorithm for counting intersections between two sets of $n$ algebraic arcs in 2D. |
| title | Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2403.12303 |