In region building, different models of cluster analysis conform to different theoretical spatial structures. The p-median model may be quite appropriate in nodal structures. Use of the p-median model, however, raises problems about the choice of the number of groups (p). This choice does not arise in facility location problems. An argument is made for parallel use of optimal methods and heuristics for region building. Optimal solutions are now feasible for even large problems because of the increase in computer power. Optimal methods provide one solution for each different value of p. Heuristic methods may provide different solutions for each value of p, depending on the starting position used for the heuristic. The multiple solutions from a heuristic procedure can then be interpreted as spatial competition between locations to become medians. By counting the number of times optimal and nonoptimal solutions are located by a heuristic procedure, statistics can be developed. Such statistics can then provide an objective method to select a specific number of groups over all others. Computational experience, with both heuristic and optimal methods, is presented.