Barequet, Gill ;
Eppstein, David ;
Goodrich, Michael T. ;
Mamano, Nil
StableMatching Voronoi Diagrams: Combinatorial Complexity and Algorithms
Abstract
We study algorithms and combinatorial complexity bounds for stablematching 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 stablematching 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 stablematching 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 realRAM model or can be approximated numerically. This is necessary, as the diagram cannot be computed exactly in an algebraic model of computation.
BibTeX  Entry
@InProceedings{barequet_et_al:LIPIcs:2018:9093,
author = {Gill Barequet and David Eppstein and Michael T. Goodrich and Nil Mamano},
title = {{StableMatching Voronoi Diagrams: Combinatorial Complexity and Algorithms}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {89:189:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9093},
URN = {urn:nbn:de:0030drops90937},
doi = {10.4230/LIPIcs.ICALP.2018.89},
annote = {Keywords: Voronoi diagram, stable matching, combinatorial complexity, lower bounds}
}
04.07.2018
Keywords: 

Voronoi diagram, stable matching, combinatorial complexity, lower bounds 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 