Least-squares assignments are a common way to partition a data set in clustering applications. While the combined choice of best clusters and representative sites is a known hard problem, linear programming methods and polyhedral theory provide insight into closely related tasks. We show that it is efficient to decide whether a given clustering can be represented as a least-squares assignment, and extend the related algorithm to arrive at soft-margin multiclass support vector machines. Further, we connect the search for optimal sites for a given clustering to volume computations for normal cones of an associated vertex in a certain polyhedron. This leads to new measures for the robustness of clusterings and explains why popular algorithms like k-means work well in practice.