2026-08-12T06:26:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9093 2024-03-06T10:43:20Z ddc:004 open_access

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms Barequet, Gill Eppstein, David Goodrich, Michael T. Mamano, Nil Voronoi diagram stable matching combinatorial complexity lower bounds 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 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 classic post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. We show that a stable-matching Voronoi diagram of n sites has O(n^{2+epsilon}) faces and edges, for any epsilon>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, where f(n) is the runtime of a geometric primitive that can be performed in the real-RAM model or can be approximated numerically. This is necessary, as the diagram cannot be computed exactly in an algebraic model of computation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gill Barequet and David Eppstein and Michael T. Goodrich and Nil Mamano 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.89 urn:nbn:de:0030-drops-90937 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.89 eng https://creativecommons.org/licenses/by/3.0/legalcode