In this talk, we discuss the proper way to generalize Voronoi diagram to regions of any prespecified size. After we propose our candidate generalization, the stable-matching Voronoi diagrams, we discuss its combinatorial complexity, that is, we give upper and lower bounds for the number of faces, edges, and vertices of the diagram.
Based on unpublished work by Gill Barequet, David Eppstein, Michael Goodrich, and Nil Mamano