- Algorithms for stable matching and clustering in a grid.
D. Eppstein, M. T. Goodrich, and N. Mamano.
arXiv:1704.02303
Proc. 18th International Workshop on Combinatorial Image Analysis (IWCIA 2017), Plovdiv, Bulgaria, 2017.
Springer, Lecture Notes in Comp. Sci. 10256 (2017), pp. 117–131.Motivated by redistricting, we consider geometric variants of the stable matching problem in which points (such as the pixels of a discretization of the unit square) are to be matched to a smaller number of centers such that each center has the same number of matches and no match is unstable with respect to Euclidean distances. We show how to solve such problems in polylogarithmic time per matched point, experiment with practical heuristics for solving these problems, and test methods for moving the centers to improve the shape of the matched regions.