We study algorithms and combinatorial complexity bounds for
stable-matching Voronoi diagrams, where a set, S, of n point sites in
the plane determines a stable matching between the points in the plane
and the sites in S such that (i) the points prefer sites closer to
them and sites prefer points closer to them, and (ii) each site has a
quota or “appetite” indicating the area of the set of points that can
be matched to it. Thus, a stable-matching Voronoi diagram is a
solution to the well-known post office problem with the added
(realistic) constraint that each post office has a limit on the size
of its jurisdiction. Previous work on the stable-matching Voronoi
diagram provided existence and uniqueness proofs, but did not analyze
its combinatorial or algorithmic complexity. In this paper, we study
the combinatorial complexity of such structures. We also provide a
discrete algorithm for constructing it in the real-RAM model of
computation.

Joint work with Gill Barequet, David Eppstein, and Nil Mamano