## Sept 30, 2016:

#
Algorithms for Stable Matching and Clustering in a Grid

## Nil Mamano

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 nxn 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.

Joint work with David Eppstein and Michael Goodrich.