  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.
