{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:36Z","timestamp":1760441256572},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_27","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T11:37:06Z","timestamp":1415965026000},"page":"338-350","source":"Crossref","is-referenced-by-count":8,"title":["On the Most Likely Voronoi Diagramand Nearest Neighbor Searching"],"prefix":"10.1007","author":[{"given":"Subhash","family":"Suri","sequence":"first","affiliation":[]},{"given":"Kevin","family":"Verbeek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"key":"27_CR1","volume-title":"Handbook of Discrete and Computational Geometry","author":"P Agarwal.","year":"2004.","unstructured":"Agarwal., P.: Range Searching. In: Goodman, J., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, New York (2004.)"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P., Aronov, B., Har-Peled, S., Phillips, J., Yi, K., Zhang, W.: Nearest neighbor searching under uncertainty II. In: Proc. 32nd PODS, pp. 115\u2013126 (2013)","DOI":"10.1145\/2463664.2465219"},{"issue":"4","key":"27_CR3","first-page":"43","volume":"8","author":"P Agarwal","year":"2012","unstructured":"Agarwal, P., Cheng, S., Yi, K.: Range searching on uncertain data. ACM Trans. on Alg. 8(4), 43 (2012)","journal-title":"ACM Trans. on Alg."},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Agarwal, P., Efrat, A., Sankararaman, S., Zhang, W.: Nearest-neighbor searching under uncertainty. In: Proc. 31st PODS, pp. 225\u2013236 (2012)","DOI":"10.1145\/2213556.2213588"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Aggarwal, C.: Managing and Mining Uncertain Data. Advances in Database Systems, 1st edn., vol. 35. Springer (2009)","DOI":"10.1007\/978-0-387-09690-2_5"},{"issue":"5","key":"27_CR6","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1109\/TKDE.2008.190","volume":"21","author":"C Aggarwal","year":"2009","unstructured":"Aggarwal, C., Yu, P.: A survey of uncertain data algorithms and applications. IEEE Trans. Knowl. Data Eng. 21(5), 609\u2013623 (2009)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"27_CR7","first-page":"57","volume":"1","author":"M Berg de","year":"2010","unstructured":"de Berg, M., Haverkort, H., Tsirogiannis, C.: Visibility maps of realistic terrains have linear smoothed complexity. J. of Comp. Geom. 1(1), 57\u201371 (2010)","journal-title":"J. of Comp. Geom."},{"issue":"8","key":"27_CR8","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.comgeo.2008.10.005","volume":"42","author":"S Chaudhuri","year":"2009","unstructured":"Chaudhuri, S., Koltun, V.: Smoothed analysis of probabilistic roadmaps. Comp. Geom. Theor. Appl. 42(8), 731\u2013747 (2009)","journal-title":"Comp. Geom. Theor. Appl."},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Welzl, E.: Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom. 4, 467\u2013489 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"7","key":"27_CR10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/1538788.1538810","volume":"52","author":"N Dalvi","year":"2009","unstructured":"Dalvi, N., R\u00e9, C., Suciu, D.: Probabilistic databases: diamonds in the dirt. Communications of the ACM 52(7), 86\u201394 (2009)","journal-title":"Communications of the ACM"},{"key":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-540-39658-1_17","volume-title":"Algorithms - ESA 2003","author":"V Damerow","year":"2003","unstructured":"Damerow, V., Meyer auf der Heide, F., R\u00e4cke, H., Scheideler, C., Sohler, C.: Smoothed motion complexity. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 161\u2013171. Springer, Heidelberg (2003)"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-540-30140-0_25","volume-title":"Algorithms \u2013 ESA 2004","author":"V Damerow","year":"2004","unstructured":"Damerow, V., Sohler, C.: Extreme points under random noise. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 264\u2013274. Springer, Heidelberg (2004)"},{"issue":"3","key":"27_CR13","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1145\/5925.5930","volume":"33","author":"L Devroye","year":"1986","unstructured":"Devroye, L.: A note on the height of binary search trees. J. ACM 33(3), 489\u2013498 (1986)","journal-title":"J. ACM"},{"key":"27_CR14","unstructured":"Evans, W., Sember, J.: Guaranteed Voronoi diagrams of uncertain sites. In: Proc. 20th CCCG, pp. 207\u2013210 (2008)"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/BF01758770","volume":"7","author":"L Guibas","year":"1992","unstructured":"Guibas, L., Knuth, D., Sharir, M.: Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 381\u2013413 (1992)","journal-title":"Algorithmica"},{"key":"27_CR16","unstructured":"J\u00f8rgensen, A., L\u00f6ffler, M., Phillips, J.: Geometric computations on indecisive and uncertain points. CoRR, abs\/1205.0273 (2012)"},{"key":"27_CR17","unstructured":"L\u00f6ffler, M.: Data imprecision in computational geometry. PhD Thesis, Utrecht University (2009)"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-008-9174-2","volume":"56","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56, 235\u2013269 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"27_CR19","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.comgeo.2012.10.010","volume":"47","author":"P Kamousi","year":"2014","unstructured":"Kamousi, P., Chan, T., Suri, S.: Closest pair and the post office problem for stochastic points. Comp. Geom. Theor. Appl. 47(2), 214\u2013223 (2014)","journal-title":"Comp. Geom. Theor. Appl."},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-540-85238-4_38","volume-title":"Mathematical Foundations of Computer Science 2008","author":"B Manthey","year":"2008","unstructured":"Manthey, B., Tantau, T.: Smoothed analysis of binary search trees and quicksort under additive noise. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 467\u2013478. Springer, Heidelberg (2008)"},{"issue":"3","key":"27_CR21","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1145\/765568.765571","volume":"50","author":"B Reed","year":"2003","unstructured":"Reed, B.: The height of a random binary search tree. J. ACM 50(3), 306\u2013332 (2003)","journal-title":"J. ACM"},{"key":"27_CR22","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D Spielman","year":"2004","unstructured":"Spielman, D., Teng, S.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51, 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"27_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/978-3-642-40450-4_67","volume-title":"Algorithms \u2013 ESA 2013","author":"S Suri","year":"2013","unstructured":"Suri, S., Verbeek, K., Y\u0131ld\u0131z, H.: On the most likely convex hull of uncertain points. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 791\u2013802. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T12:36:36Z","timestamp":1559046996000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}