Approximation of geometric dispersion problems

We consider problems of distributing a number of points within a polygonal region P, such that the points are "far away" from each other. Problems of this type have been considered before for the case where the possible locat ions form a discrete set. Dispersion problems are closely related to packin g problems. While Hochbaum and Maass [20] have given a polynomial-time appr oximation scheme for packing, we show that geometric dispersion problems ca nnot be approximated arbitrarily well in polynomial timer unless P = NP. A special case of this observation solves an open problem by Rosenkrantz et a l. [31]. We give a 5 approximation algorithm for one version of the geometr ic dispersion problem. This algorithm is strongly polynomial in the size of the input, i.e., its running time does nor depend on the area of P. We als o discuss extensions and open problems.