We study the problem of placing mobile phone antennas on a given terrain. The objective is to minimize the number of antennas that are needed to cover the whole terrain. We show that even for simple models of electromagnetic wave propagation, this optimization problem is computationally intractable. Even worse: No decent approximation can be computed in polynomial time, asymptotically in the worst case. On the positive side, we propose heuristics, and we show how they behave for real terrains (such as Switzerland) and typical wave propagation models (such as the Hata model).

More information about the speaker's research is available at his Web site, http://www.inf.ethz.ch/department/TI/pw/.