- Stable-matching Voronoi diagrams:
combinatorial complexity and algorithms.
G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.
arXiv:1804.09411
Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.
J. Computational Geometry 11 (1): 26–59, 2020.The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.