Part of Advances in Neural Information Processing Systems 28 (NIPS 2015)
Julian E. Yarkony, Charless Fowlkes
We study the problem of hierarchical clustering on planar graphs. We formulate this in terms of finding the closest ultrametric to a specified set of distances and solve it using an LP relaxation that leverages minimum cost perfect matching as a subroutine to efficiently explore the space of planar partitions. We apply our algorithm to the problem of hierarchical image segmentation.