**Abstract: **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