  The separability of clusters is one of the most desired properties in
clustering. There is a wide range of settings in which different clusterings of
the same data set appear. A common application lies in the need for a
transition of one separable clustering into another one. This transition should
be a sequence of simple, natural steps that upholds separability of the
clusters throughout.
  In this paper, we design an algorithm for such a transition. We exploit the
intimate connection of separability and linear programming over bounded-shape
partition and transportation polytopes: separable clusterings lie on the
boundary of partition polytopes, form a subset of the vertices of the
corresponding transportation polytopes, and circuits of both polytopes are
readily interpreted as sequential or cyclical exchanges of items between
clusters. This allows for a natural approach to achieve the desired transition
through a combination of two walks: an edge walk between two so-called radial
clusterings in a transportation polytope, computed through an adaptation of
classical tools of sensitivity analysis and parametric programming; and a walk
from a separable clustering to a corresponding radial clustering, computed
through a tailored, iterative routine updating cluster sizes and re-optimizing
the cluster assignment of items.
