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 R^2 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 show that a stable-matching Voronoi diagram of n point sites has O(n^{2+\varepsilon}) faces and edges, for any \varepsilon>0, and show that this bound is almost tight by giving a family of diagrams with \Theta(n^2) faces and edges. We also provide a discrete algorithm for constructing it in O(n^3  +n^2f(n)) time in the real-RAM model of computation, where f(n) is the runtime of a geometric primitive (which we identify ) that can be performed in the real-RAM model or can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation  .
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 R^2 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 show that a stable-matching Voronoi diagram of n point sites has O(n^{2+\varepsilon}) faces and edges, for any \varepsilon>0, and show that this bound is almost tight by giving a family of diagrams with \Theta(n^2) faces and edges. We also provide a discrete algorithm for constructing it in O(n^3 \log n +n^2f(n)) time in the real-RAM model of computation, where f(n) is the runtime of a geometric primitive (which we define ) that can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation . We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions .
A
\log n
R
identify
define
D
performed in the real-RAM model or can be
A
. We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions