The maximal dispersion problem and the ‘first point outside the neighbourhood’ heuristic

This paper considers the problem of selecting, from a finite set S⊆Rⁿ, endowed with a metric ||||, p maximally dispersed points. An heuristic, called the ‘first point outside the neighbourhood’ heuristic, is studied. The main results are that the dispersion, produced by the heuristic, is never worse than 1/3 of the maximal dispersion and that, for certain values of p, the dispersion obtained is not worse than 1/2 of the maximal dispersion.