Algorithms for Stable Matching and Clustering in a Grid
Skip to main content
eScholarship
Open Access Publications from the University of California

Algorithms for Stable Matching and Clustering in a Grid

  • Author(s): Eppstein, David
  • Goodrich, Michael T
  • Mamano, Nil
  • et al.
Abstract

We study a discrete version of a geometric stable marriage problem originally proposed in a continuous setting by Hoffman, Holroyd, and Peres, in which points in the plane are stably matched to cluster centers, as prioritized by their distances, so that each cluster center is apportioned a set of points of equal area. We show that, for a discretization of the problem to an $n\times n$ grid of pixels with $k$ centers, the problem can be solved in time $O(n^2 \log^5 n)$, and we experiment with two slower but more practical algorithms and a hybrid method that switches from one of these algorithms to the other to gain greater efficiency than either algorithm alone. We also show how to combine geometric stable matchings with a $k$-means clustering algorithm, so as to provide a geometric political-districting algorithm that views distance in economic terms, and we experiment with weighted versions of stable $k$-means in order to improve the connectivity of the resulting clusters.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View