Document Open Access Logo

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

Authors Gill Barequet, David Eppstein, Michael T. Goodrich, Nil Mamano

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.89.pdf
  • Filesize: 0.96 MB
  • 14 pages

Document Identifiers

Author Details

Gill Barequet
  • Technion - Israel Inst. of Technology, Haifa, Israel
David Eppstein
  • University of California, Irvine, U.S.
Michael T. Goodrich
  • University of California, Irvine, U.S.
Nil Mamano
  • University of California, Irvine, U.S.

Funding

This work was partially supported by DARPA under agreement no. AFRL FA8750-15-2-0092 and NSF grants 1228639, 1526631,2 1217322, 1618301, and 1616248. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense or the U.S. Government.

Cite As Get BibTex

Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano. Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.89

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 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Voronoi diagram
  • stable matching
  • combinatorial complexity
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P. K. Agarwal and Micha Sharir. Davenport-Schinzel Sequences and Their Geometric Applications. Technical Report DUKE-TR-1995-21, Duke University, Durham, NC, USA, 1995. Google Scholar
  2. Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, and Martin Pál. General auction mechanism for search advertising. In 18th Int. Conf. on the World Wide Web (WWW), pages 241-250. ACM, 2009. URL: http://dx.doi.org/10.1145/1526709.1526742.
  3. Franz Aurenhammer. Voronoi diagrams - A survey of a fundamental geometric data structure. ACM Computing Surveys, 23(3):345-405, 1991. URL: http://dx.doi.org/10.1145/116873.116880.
  4. Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov. Minkowski-type theorems and least-squares clustering. Algorithmica, 20(1):61-76, 1998. URL: http://dx.doi.org/10.1007/PL00009187.
  5. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. Google Scholar
  6. Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano. Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms. Electronic preprint arXiv:1804.09411, 2018. Google Scholar
  7. Priyadarshi Bhattacharya and Marina L. Gavrilova. Roadmap-based path planning - Using the Voronoi diagram for a clearance-based shortest path. IEEE Robotics Automation Magazine, 15(2):58-66, 2008. URL: http://dx.doi.org/10.1109/MRA.2008.921540.
  8. Jonathan W. Brandt and V. Ralph Algazi. Continuous skeleton computation by Voronoi diagram. CVGIP: Image Understanding, 55(3):329-338, 1992. URL: http://dx.doi.org/10.1016/1049-9660(92)90030-7.
  9. David Eppstein, Michael T. Goodrich, Doruk Korkmaz, and Nil Mamano. Defining equitable geographic districts in road networks via stable matching. In 25th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems, 2017. Google Scholar
  10. David Eppstein, Michael T. Goodrich, and Nil Mamano. Algorithms for stable matching and clustering in a grid. In 18th Int. Workshop on Combinatorial Image Analysis (IWCIA), volume 10256 of LNCS, pages 117-131. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59108-7_10.
  11. Steven Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2(2):153-174, 1987. URL: http://dx.doi.org/10.1007/BF01840357.
  12. David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. URL: http://dx.doi.org/10.2307/2312726.
  13. Ihor G. Gowda, David G. Kirkpatrick, Der Tsai Lee, and Amnon Naamad. Dynamic Voronoi diagrams. IEEE Transactions on Information Theory, 29(5):724-731, September 1983. URL: http://dx.doi.org/10.1109/TIT.1983.1056738.
  14. Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, USA, 1989. Google Scholar
  15. Christopher Hoffman, Alexander E. Holroyd, and Yuval Peres. A stable marriage of Poisson and Lebesgue. Annals of Probability, 34(4):1241-1272, 2006. URL: http://dx.doi.org/10.1214/009117906000000098.
  16. Kazuo Iwama and Shuichi Miyazaki. A survey of the stable marriage problem and its variants. In IEEE Int. Conf. on Informatics Education and Research for Knowledge-Circulating Society (ICKS), pages 131-136, 2008. URL: http://dx.doi.org/10.1109/ICKS.2008.7.
  17. Klara Kedem, Ron Livné, János Pach, and Micha Sharir. On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom., 1(1):59-71, 1986. URL: http://dx.doi.org/10.1007/BF02187683.
  18. Koichi Kise, Akinori Sato, and Motoi Iwata. Segmentation of page images using the area Voronoi diagram. Computer Vision and Image Understanding, 70(3):370-382, 1998. URL: http://dx.doi.org/10.1006/cviu.1998.0684.
  19. Donald E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, MA, 2nd edition, 1998. Google Scholar
  20. Seapahn Meguerdichian, Farinaz Koushanfar, Gang Qu, and Miodrag Potkonjak. Exposure in wireless ad-hoc sensor networks. In 7th Int. Conf. on Mobile Computing and Networking (MobiCom), pages 139-150. ACM, 2001. URL: http://dx.doi.org/10.1145/381677.381691.
  21. National Resident Matching Program, 2017. URL: http://www.nrmp.org.
  22. Martin Petřek, Pavlína Košinová, Jaroslav Koča, and Michal Otyepka. MOLE: A Voronoi diagram-based explorer of molecular channels, pores, and tunnels. Structure, 15(11):1357-1363, 2007. URL: http://dx.doi.org/10.1016/j.str.2007.10.007.
  23. Alvin E. Roth and Marilda Sotomayor. The college admissions problem revisited. Econometrica, 57(3):559-570, 1989. URL: http://dx.doi.org/10.2307/1911052.
  24. Ivan Stojmenović, Anand Prakash Ruhil, and D. K. Lobiyal. Voronoi diagram and convex hull based geocasting and routing in wireless networks. Wireless Communications and Mobile Computing, 6(2):247-258, 2006. URL: http://dx.doi.org/10.1002/wcm.384.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact