TY - GEN
T1 - Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
AU - Chan, Timothy M.
AU - Cheng, Pingan
AU - Zheng, Da Wei
N1 - Timothy M. Chan: Work supported by NSF Grant CCF-2224271. Pingan Cheng: Work supported by DFF (Det Frie Forskningsr\u00E5d) of Danish Council for Independent Research under grant ID DFF\u20137014\u201300404 and STIBOFONDENs IT-rejsestipendier til ph.d.studerende during the author\u2019s visit to UIUC.
PY - 2024/6
Y1 - 2024/6
N2 - 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(n3/2+ε) preprocessing time and space, so that we can count the number of ranges containing a query point in O(n1/4+ε) time, for an arbitrarily small constant ε > 0. (The query time bound is likely close to tight for this space bound.) 2. Ray shooting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n3/2+ε) preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in O(n1/4+ε) time. (The query bound is again likely close to tight for this space bound, and they improve a result by Ezra and Sharir with near n3/2 space and near √n query time.) 3. Intersection counting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n3/2+ε) 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(n1/2+ε) time. In particular, this implies an O(n3/2+ε)-time algorithm for counting intersections between two sets of n algebraic arcs in 2D. (This generalizes a classical O(n3/2+ε)-time algorithm for circular arcs by Agarwal and Sharir from SoCG 1991.).
AB - 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(n3/2+ε) preprocessing time and space, so that we can count the number of ranges containing a query point in O(n1/4+ε) time, for an arbitrarily small constant ε > 0. (The query time bound is likely close to tight for this space bound.) 2. Ray shooting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n3/2+ε) preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in O(n1/4+ε) time. (The query bound is again likely close to tight for this space bound, and they improve a result by Ezra and Sharir with near n3/2 space and near √n query time.) 3. Intersection counting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n3/2+ε) 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(n1/2+ε) time. In particular, this implies an O(n3/2+ε)-time algorithm for counting intersections between two sets of n algebraic arcs in 2D. (This generalizes a classical O(n3/2+ε)-time algorithm for circular arcs by Agarwal and Sharir from SoCG 1991.).
KW - Computational geometry
KW - data structures
KW - intersection searching
KW - polynomial partitioning
KW - range searching
KW - semialgebraic sets
UR - https://www.scopus.com/pages/publications/85195478162
UR - https://www.scopus.com/pages/publications/85195478162#tab=citedBy
U2 - 10.4230/LIPIcs.SoCG.2024.33
DO - 10.4230/LIPIcs.SoCG.2024.33
M3 - Conference contribution
AN - SCOPUS:85195478162
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 40th International Symposium on Computational Geometry, SoCG 2024
A2 - Mulzer, Wolfgang
A2 - Phillips, Jeff M.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 40th International Symposium on Computational Geometry, SoCG 2024
Y2 - 11 June 2024 through 14 June 2024
ER -