Given a set $S$ of $n$ points in the plane, representing a set of {\em sensors}, and given a communication range $r\geq 1$, we are interested in the relay placement problem: Determine a minimum-cardinaltiy set $R$ of {\em relays} so that between every pair of sensors there exists a path of communication through sensors and/or relays. Two relays can communicate if they are within distance $r$ of each other; two sensors, or a relay and a sensor, can communicate if they are within distance 1 of each other. In the one-tier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors there exists a path that is allowed to use both sensors and relays. The two-tier version adds the restriction that the path between two sensors must go through only relays, without using sensors as intermediate nodes. We present improved constant-factor approximation algorithms for the one-tier version and a PTAS for the two-tier version. Further, we show that there is no PTAS for the one-tier version (for general $r$), assuming P${}\ne{}$NP.

This is joint work with Alon Efrat, Sandor Fekete, Valentin Polishchuk, G. R. Poornananda, and Jukka Suomela.