  The rules governing the availability and quality of connections in a wireless
network are described by physical models such as the signal-to-interference &
noise ratio (SINR) model. For a collection of simultaneously transmitting
stations in the plane, it is possible to identify a reception zone for each
station, consisting of the points where its transmission is received correctly.
The resulting SINR diagram partitions the plane into a reception zone per
station and the remaining plane where no station can be heard.
  SINR diagrams appear to be fundamental to understanding the behavior of
wireless networks, and may play a key role in the development of suitable
algorithms for such networks, analogous perhaps to the role played by Voronoi
diagrams in the study of proximity queries and related issues in computational
geometry. So far, however, the properties of SINR diagrams have not been
studied systematically, and most algorithmic studies in wireless networking
rely on simplified graph-based models such as the unit disk graph (UDG) model,
which conveniently abstract away interference-related complications, and make
it easier to handle algorithmic issues, but consequently fail to capture
accurately some important aspects of wireless networks.
  The current paper focuses on obtaining some basic understanding of SINR
diagrams, their properties and their usability in algorithmic applications.
Specifically, based on some algebraic properties of the polynomials defining
the reception zones we show that assuming uniform power transmissions, the
reception zones are convex and relatively well-rounded. These results are then
used to develop an efficient approximation algorithm for a fundamental point
location problem in wireless networks.
