Document Open Access Logo

Most Likely Voronoi Diagrams in Higher Dimensions

Authors Nirman Kumar, Benjamin Raichel, Subhash Suri, Kevin Verbeek

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.31.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Nirman Kumar
Benjamin Raichel
Subhash Suri
Kevin Verbeek

Cite AsGet BibTex

Nirman Kumar, Benjamin Raichel, Subhash Suri, and Kevin Verbeek. Most Likely Voronoi Diagrams in Higher Dimensions. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FSTTCS.2016.31

Abstract

The Most Likely Voronoi Diagram is a generalization of the well known Voronoi Diagrams to a stochastic setting, where a stochastic point is a point associated with a given probability of existence, and the cell for such a point is the set of points which would classify the given point as its most likely nearest neighbor. We investigate the complexity of this subdivision of space in d dimensions. We show that in the general case, the complexity of such a subdivision is Omega(n^{2d}) where n is the number of points. This settles an open question raised in a recent (ISAAC 2014) paper of Suri and Verbeek, which first defined the Most Likely Voronoi Diagram. We also show that when the probabilities are assigned using a random permutation of a fixed set of values, in expectation the complexity is only ~O(n^{ceil{d/2}}) where the ~O(*) means that logarithmic factors are suppressed. In the worst case, this bound is tight up to polylog factors.
Keywords
  • Uncertainty
  • Lower bounds
  • Voronoi Diagrams
  • Stochastic

Metrics

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

References

  1. A. Abdullah, S. Daruki, and J. M. Phillips. Range counting coresets for uncertain data. In Proc. 29th Annu. Sympos. Comput. Geom., pages 223-232. ACM, 2013. Google Scholar
  2. P. Afshani, P. K. Agarwal, L. Arge, K. G. Larsen, and J. M. Phillips. (Approximate) uncertain skylines. Theory of Comput. Syst., 52:342-366, 2013. Google Scholar
  3. 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 PODS, pages 115-126, 2013. Google Scholar
  4. P. K. Agarwal, S.-W. Cheng, and K. Yi. Range searching on uncertain data. ACM Trans. on Algorithms, 8(4):43:1-43:17, 2012. Google Scholar
  5. P. K. Agarwal, A. Efrat, S. Sankararaman, and W. Zhang. Nearest-neighbor searching under uncertainty. In Proc. 31st ACM PODS, pages 225-236. ACM, 2012. Google Scholar
  6. P. K. Agarwal, S. Har-Peled, S. Suri, H. Yıldız, and W. Zhang. Convex hulls under uncertainty. In Proc. 22nd ESA, pages 37-48, 2014. Google Scholar
  7. C. C. Aggarwal. Managing and Mining Uncertain Data. Springer, 2009. Google Scholar
  8. C. C. Aggarwal and P. S. Yu. A survey of uncertain data algorithms and applications. IEEE TKDE., 21(5):609-623, 2009. Google Scholar
  9. A. Agrawal, S. Rahul, Y. Li, J. Xue, and R. Janardan. Skyline problems for stochastic points: Algorithms and hardness results. Unpublished manuscript (personal communication), 2015. Google Scholar
  10. Z. Bai, L. Devroye, H. Hwang, and T. Tsai. Maxima in hypercubes. Random Structures &Algorithms, 27(3):290-309, 2005. Google Scholar
  11. M. de Berg, A. D. Mehrabi, and F. Sheikhi. Separability of imprecise points. In Proc. 14th SWAT, pages 146-157. Springer, 2014. Google Scholar
  12. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag New York, Inc., 1987. Google Scholar
  13. M. Fink, J. Hershberger, N. Kumar, and S. Suri. Hyperplane separability and convexity of probabilistic point sets. In Proc. 32nd Annu. Sympos. Comput. Geom., pages 38:1-38:16, 2016. Google Scholar
  14. S. Har-Peled and B. Raichel. On the complexity of randomly weighted Voronoi diagrams. In Proc. 30th Annu. Sympos. Comput. Geom., pages 232-241, 2014. Google Scholar
  15. A. Jørgensen, M. Löffler, and J. M. Phillips. Geometric computations on indecisive and uncertain points. CoRR, abs/1205.0273, 2012. Google Scholar
  16. P. Kamousi, T. M. Chan, and S. Suri. Stochastic minimum spanning trees in Euclidean spaces. In Proc. 27th Annu. Sympos. Comput. Geom., pages 65-74, 2011. Google Scholar
  17. P. Kamousi, T. M. Chan, and S. Suri. Closest pair and the post office problem for stochastic points. Comput. Geom. Theory Appl., 47(2):214-223, 2014. Google Scholar
  18. H. Kaplan, E. Ramos, and M. Sharir. The overlay of minimization diagrams in a randomized incremental construction. Discrete Comput. Geom., 45(3):371-382, 2011. Google Scholar
  19. A. I. Kuksa and N. Z. Šor. The method of estimating the number of conditionally optimal trajectories of discrete separable dynamic programming (in russian). Kibernetika (Kiev), 6:37-44, 1972. Google Scholar
  20. N. Kumar and S. Suri. Containment and evasion in stochastic point data. In Proc. 12th Latin Am. Th. Infor. Sympos., pages 576-589, 2016. Google Scholar
  21. Y. Li, J. Xue, A. Agrawal, and R. Janardan. On the arrangement of stochastic lines in R². Unpublished manuscript (personal communication), 2015. Google Scholar
  22. J. Matoušek. Lectures on Discrete Geometry, volume 212 of Grad. Text in Math. Springer, 2002. URL: http://kam.mff.cuni.cz/~matousek/dg.html.
  23. K. Agarwal P. and M. Sharir. Arrangements and their applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 49-119. North-Holland, 2000. URL: http://www.cs.duke.edu/~pankaj/papers/arrangement-survey.ps.gz.
  24. S. Suri and K. Verbeek. On the most likely voronoi diagram and nearest neighbor searching. In Proceedings of the 25th Int. Sympos. Alg. and Comp. (ISAAC 2014), pages 338-350, 2014. Google Scholar
  25. J. Xue, Y. Li, and R. Janardan. On the separability of stochastic geometric objects, with applications. In Proc. 32nd Annu. Sympos. Comput. Geom., pages 62:1-62:16, 2016. 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 Imprint Privacy Contact