A Survey of Algorithms for Contiguity-constrained Clustering and Related Problems

A large number of non-parametric clustering algorithms from a wide range of applications in the social sciences, earth sciences, pattern recognition, and image processing, are critically appraised. These algorithms all have the common property of seeking to use a relational-usually contiguity-constraint, in addition to proximity information. The constraint is necessary in many applications for the visualization of clustering results. The primary objective of this survey is to sketch out the major algorithmic paradigms in current use, with a view towards facilitating the task of algorithm design in this area.