Speaker: Matya Katz (BGU)

Title: Batched Point Location in SINR Diagrams via Algebraic Tools
<http://www.cs.bgu.ac.il/~matya/Courses/DCG_seminar/abs_4.11.2015>


Abstract: 
The SINR model for the quality of wireless connections has been
the subject of extensive recent study. It attempts to predict whether
a particular transmitter is heard at a specific location, in a setting consisting
of n simultaneous transmitters and background noise. The SINR model gives rise to
a natural geometric object, the SINR diagram, which partitions the space into
n regions where each of the transmitters can be heard and the remaining space
where no transmitter can be heard.

Efficient point location in the SINR diagram, i.e., being able to build
a data structure that facilitates determining, for a query point, whether
any transmitter is heard there, and if so, which one, has been recently 
investigated in several papers. These planar data structures are constructed
in time at least quadratic in n and support logarithmic-time approximate queries.

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. These results demonstrate the (so far underutilized) power of
combining algebraic tools with those of computational geometry and other fields.

Based on work with Boris Aronov