  The SINR model for wireless networks has been extensively studied recently.
It tries to model whether a particular transmitter is heard at a specific
location, with $n$ transmitting simultaneously. The SINR diagram consists of
$n$ regions where each transmitter can be heard and the remaining space where
no one can be heard.
  Efficient point location in the SINR diagram, i.e., building a data structure
to determine, for a query point, whether any transmitter is heard there, and if
so, which one, has been recently investigated. Previous such planar data
structures are constructed in time at least quadratic in $n$ and support
logarithmic-time approximate queries. Moreover, the performance of these
depends not only on the number $n$ of transmitters and on the approximation
parameter $\varepsilon$, but also on some geometric parameters that cannot be
bounded a priori as a function of $n$ or $\varepsilon$.
  We address the question of batched point location queries, i.e., answering
many queries simultaneously. Specifically, in one dimension, we can answer $n$
queries exactly in amortized polylogarithmic time per query, while in the plane
we can do it approximately.
  All these results can handle arbitrary power assignments to the transmitters.
Moreover, the amortized query time in these results depends only on $n$ and
$\varepsilon$.
  We also show how to speed up the preprocessing in a previously proposed
point-location structure in SINR diagram for uniform-power sites, by almost a
full order of magnitude. For this we obtain results on the sensitivity of the
reception regions to slight changes in the reception threshold, which are of
independent interest.
  Finally, these results demonstrate the (so far underutilized) power of
combining algebraic tools with those of computational geometry and other
fields.
