Document Open Access Logo

From Proximity to Utility: A Voronoi Partition of Pareto Optima

Authors Hsien-Chih Chang, Sariel Har-Peled, Benjamin Raichel

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.689.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Hsien-Chih Chang
Sariel Har-Peled
Benjamin Raichel

Cite As Get BibTex

Hsien-Chih Chang, Sariel Har-Peled, and Benjamin Raichel. From Proximity to Utility: A Voronoi Partition of Pareto Optima. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 689-703, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.689

Abstract

We present an extension of Voronoi diagrams where not only the distance to the site is taken into account when considering which site the client is going to use, but additional attributes (i.e., prices or weights) are also considered. A cell in this diagram is then the loci of all clients that consider the same set of sites to be relevant.  In particular, the precise site a client might use from this candidate set depends on parameters that might change between usages, and the candidate set lists all of the relevant sites. The resulting diagram is significantly more expressive than Voronoi diagrams, but naturally has the drawback that its complexity, even in the plane, might be quite high. Nevertheless, we show that if the attributes of the sites are drawn from the same distribution (note that the locations are fixed), then the expected complexity of the candidate diagram is near linear. To this end, we derive several new technical results, which are of independent interest.

Subject Classification

Keywords
  • Voronoi diagrams
  • expected complexity
  • backward analysis
  • Pareto optima
  • candidate diagram
  • Clarkson-Shor technique

Metrics

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

References

  1. P. K. Agarwal, B. Aronov, S. Har-Peled, J. M. Phillips, K. Yi, and W. Zhang. Nearest neighbor searching under uncertainty II. In Proc. 32nd ACM Sympos. Principles Database Syst.\CNFPODS, pages 115-126, 2013. Google Scholar
  2. P. K. Agarwal, S. Har-Peled, H. Kaplan, and M. Sharir. Union of random minkowski sums and network vulnerability analysis. Discrete Comput. Geom., 52(3):551-582, 2014. Google Scholar
  3. P. K. Agarwal, J. Matoušek, and O. Schwarzkopf. Computing many faces in arrangements of lines and segments. SIAM J. Comput., 27(2):491-505, 1998. Google Scholar
  4. F. Aurenhammer, R. Klein, and D.-T. Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. Google Scholar
  5. F. Aurenhammer and O. Schwarzkopf. A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Internat. J. Comput. Geom. Appl., pages 363-381, 1992. Google Scholar
  6. Z.-D. Bai, L. Devroye, H.-K. Hwang, and T.-H. Tsai. Maxima in hypercubes. Random Struct. Alg., 27(3):290-309, 2005. Google Scholar
  7. I. Bárány and M. Reitzner. On the variance of random polytopes. Adv. Math., 225(4):1986-2001, 2010. Google Scholar
  8. I. Bárány and M. Reitzner. Poisson polytopes. Annals. Prob., 38(4):1507-1531, 2010. Google Scholar
  9. M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. Google Scholar
  10. S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In Proc. 17th IEEE Int. Conf. Data Eng., pages 421-430, 2001. Google Scholar
  11. H.-C. Chang, S. Har-Peled, and B. Raichel. From proximity to utility: A Voronoi partition of Pareto optima. CoRR, abs/1404.3403, 2014. Google Scholar
  12. B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990. Google Scholar
  13. K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comput. Geom. Theory Appl., 3(4):185-212, 1993. Google Scholar
  14. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989. Google Scholar
  15. A. Feldman. Welfare economics. In S. Durlauf and L. Blume, editors, The New Palgrave Dictionary of Economics. Palgrave Macmillan, 2008. Google Scholar
  16. P. Godfrey, R. Shipley, and J. Gryz. Algorithms and analyses for maximal vector computation. VLDB J., 16(1):5-28, 2007. Google Scholar
  17. S. Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. Amer. Math. Soc., 2011. Google Scholar
  18. S. Har-Peled and B. Raichel. On the expected complexity of randomly weighted Voronoi diagrams. In Proc. 30th Annu. Sympos. Comput. Geom.\CNFSoCG, pages 232-241, 2014. Google Scholar
  19. D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987. Google Scholar
  20. H.-K. Hwang, T.-H. Tsai, and W.-M. Chen. Threshold phenomena in k-dominant skylines of random samples. SIAM J. Comput., 42(2):405-441, 2013. Google Scholar
  21. H. Kung, F. Luccio, and F. Preparata. On finding the maxima of a set of vectors. J. Assoc. Comput. Mach., 22(4):469-476, 1975. Google Scholar
  22. T. Ottmann, E. Soisalon-Soininen, and D. Wood. On the definition and computation of rectlinear convex hulls. Inf. Sci., 33(3):157-171, 1984. Google Scholar
  23. R. Schneider and J. A. Wieacker. Integral geometry. In P. M. Gruber and J. M. Wills, editors, Handbook of Convex Geometry, volume B, chapter 5.1, pages 1349-1390. North-Holland, 1993. Google Scholar
  24. R. Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics, pages 37-68. Springer-Verlag, 1993. Google Scholar
  25. M. Sharir. The Clarkson-Shor technique revisited and extended. Comb., Prob. & Comput., 12(2):191-201, 2003. Google Scholar
  26. M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995. Google Scholar
  27. W. Weil and J. A. Wieacker. Stochastic geometry. In P. M. Gruber and J. M. Wills, editors, Handbook of Convex Geometry, volume B, chapter 5.2, pages 1393-1438. North-Holland, 1993. Google Scholar
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