Clyde F. Martin
Department of Mathematics
Texas Tech. University
Lubbock, Texas, USA
Suppose we are given a mob of robots that cannot communicate with each other if they are closer together than r meters and that their communications systems only have a range of R meters. For tactical purposes it is often convenient that every robot be able to communicate directly with every other robot in the mob. The question arises of how many robots can be used and still meet these distance constraints. The problem can be directly phrased as a min-max optimization problem but as such is nontrivial to solve. However, it is clearly closely related to the problem of circle packing. The circle packing problem has been studied for many years and, interestingly, is not solved in any precise sense. The circle packing problem is dual, in some sense, to the communication problem. The circle packing problem is usually stated as "Determine the smallest circle in which n unit circles can be places without overlap". We will show in this talk that given known results from the circle packing problem satisfactory answers can be obtained for the communications problem.
This is joint work with Magnus Egerstedt.