{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T06:14:02Z","timestamp":1785392042692,"version":"3.55.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,15]],"date-time":"2016-08-15T00:00:00Z","timestamp":1471219200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,8,15]],"date-time":"2016-08-15T00:00:00Z","timestamp":1471219200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["CCF-09-40671"],"award-info":[{"award-number":["CCF-09-40671"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-10-12254"],"award-info":[{"award-number":["CCF-10-12254"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CCF-11-61359"],"award-info":[{"award-number":["CCF-11-61359"]}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-07-1-0376"],"award-info":[{"award-number":["W911NF-07-1-0376"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-08-1-0452"],"award-info":[{"award-number":["W911NF-08-1-0452"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006531","name":"Energy Research and Development Center, Missouri University of Science and Technology","doi-asserted-by":"publisher","award":["W9132V-11-C-0003"],"award-info":[{"award-number":["W9132V-11-C-0003"]}],"id":[{"id":"10.13039\/100006531","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-09-15984"],"award-info":[{"award-number":["CCF-09-15984"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-12-17462"],"award-info":[{"award-number":["CCF-12-17462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CCF-1161495"],"award-info":[{"award-number":["CCF-1161495"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1035917"],"award-info":[{"award-number":["CNS-1035917"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0195-y","type":"journal-article","created":{"date-parts":[[2016,8,15]],"date-time":"2016-08-15T14:41:22Z","timestamp":1471272082000},"page":"340-367","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Convex Hulls Under Uncertainty"],"prefix":"10.1007","volume":"79","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hakan","family":"Y\u0131ld\u0131z","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wuzhou","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,15]]},"reference":[{"issue":"3","key":"195_CR1","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/s00224-012-9382-7","volume":"52","author":"P Afshani","year":"2012","unstructured":"Afshani, P., Agarwal, P.K., Arge, L., Larsen, K.G., Phillips, J.M.: (Approximate) uncertain skylines. Theory Comput. Syst. 52(3), 342\u2013366 (2012)","journal-title":"Theory Comput. Syst."},{"key":"195_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Aronov, B., Har-Peled, S., Phillips, J.M., Yi, K., Zhang, W.: Nearest neighbor searching under uncertainty II. In: Proceedings of 32nd ACM Symposium Principles on Database System, pp. 115\u2013126 (2013)","DOI":"10.1145\/2463664.2465219"},{"issue":"4","key":"195_CR3","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/2344422.2344433","volume":"8","author":"PK Agarwal","year":"2012","unstructured":"Agarwal, P.K., Cheng, S.-W., Yi, K.: Range searching on uncertain data. ACM Trans. Algorithms 8(4), 43:1\u201343:17 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"195_CR4","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K. , Efrat, A., Sankararaman, S., Zhang, W.: Nearest-neighbor searching under uncertainty. In: Proceedings of 31st ACM Symposium Principles Database Systems, pp. 225\u2013236 (2012)","DOI":"10.1145\/2213556.2213588"},{"key":"195_CR5","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv. 30, 412\u2013458 (1998)","journal-title":"ACM Comput. Surv."},{"key":"195_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/B978-044482537-7\/50003-6","volume-title":"Handbook of Computational Geometry","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49\u2013119. Elsevier Science Publishers B.V. North-Holland, Amsterdam (2000)"},{"issue":"1","key":"195_CR7","first-page":"5:1","volume":"5","author":"PK Agarwal","year":"2008","unstructured":"Agarwal, P.K., Sharir, M., Welzl, E.: Algorithms for center and Tverberg points. ACM Trans. Algorithms 5(1), 5:1\u20135:20 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"195_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.jalgor.2004.06.009","volume":"62","author":"S Cabello","year":"2007","unstructured":"Cabello, S.: Approximation algorithms for spreading points. J. Algorithms 62(2), 49\u201373 (2007)","journal-title":"J. Algorithms"},{"issue":"1","key":"195_CR9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(1), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"195_CR10","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B Chazelle","year":"1985","unstructured":"Chazelle, B., Guibas, L.J., Lee, D.T.: The power of geometric duality. BIT 25(1), 76\u201390 (1985)","journal-title":"BIT"},{"issue":"2","key":"195_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"7","key":"195_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/1538788.1538810","volume":"52","author":"NN Dalvi","year":"2009","unstructured":"Dalvi, N.N., R\u00e9, C., Suciu, D.: Probabilistic databases: diamonds in the dirt. Comm. ACM 52(7), 86\u201394 (2009)","journal-title":"Comm. ACM"},{"key":"195_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"195_CR14","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/B978-0-444-89596-7.50017-1","volume-title":"Handbook of Convex Geometry","author":"J Eckhoff","year":"1993","unstructured":"Eckhoff, J.: Helly, radon, and Carath\u00e9odory type theorems. In: Gruber, P.M., Wills, J.M. (eds.) Handbook of Convex Geometry, pp. 389\u2013448. North-Holland, Amsterdam (1993)"},{"key":"195_CR15","doi-asserted-by":"crossref","unstructured":"Evans, W.S., Gansner, E.R., Kaufmann, M., Liotta, G., Meijer, H., Spillner, A.: Approximate proximity drawings. In : Proceedings of 19th International Symposium on Graph Drawing, pp. 166\u2013178 (2011)","DOI":"10.1007\/978-3-642-25878-7_17"},{"key":"195_CR16","unstructured":"Fink, M., Hershberger, J., Kumar, N., Suri, S.: Hyperplane separability and convexity of probabilistic point sets. In: Proceedings of 32nd Annual Symposium on Computational Geometry, pp. 38:1\u201338:16 (2016)"},{"issue":"2","key":"195_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1142\/S0218195994000100","volume":"4","author":"PG Franciosa","year":"1994","unstructured":"Franciosa, P.G., Gaibisso, C., Gambosi, G., Talamo, M.: A convex hull algorithm for points with approximately known positions. Int. J. Comput. Geometry Appl. 4(2), 153\u2013163 (1994)","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"6","key":"195_CR18","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1007\/BF01190154","volume":"9","author":"LJ Guibas","year":"1993","unstructured":"Guibas, L.J., Salesin, D., Stolfi, J.: Constructing strongly convex approximate hulls with inaccurate primitives. Algorithmica 9(6), 534\u2013560 (1993)","journal-title":"Algorithmica"},{"key":"195_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"195_CR20","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A., L\u00f6ffler, M., Phillips, J.: Geometric computations on indecisive points. In: Proceedings of 12th Workshop on Algorithms and Data Structures, pp. 536\u2013547 (2011)","DOI":"10.1007\/978-3-642-22300-6_45"},{"issue":"2","key":"195_CR21","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.M., Suri, S.: Closest pair and the post office problem for stochastic points. Comput. Geom. Theory Appl. 47(2), 214\u2013223 (2014)","journal-title":"Comput. Geom. Theory Appl."},{"key":"195_CR22","doi-asserted-by":"crossref","unstructured":"Kamousi, P., Chan, T.M., Suri, S.: Stochastic minimum spanning trees in euclidean spaces. In: Proceedings of 27th Annual Symposium on Computational Geometry, pp. 65\u201374 (2011)","DOI":"10.1145\/1998196.1998206"},{"key":"195_CR23","unstructured":"L\u00f6ffler, M.: Data imprecision in computational geometry. PhD Thesis, Department of Computer Science, Utrecht University (2009)"},{"key":"195_CR24","doi-asserted-by":"crossref","unstructured":"L\u00f6ffler, M., Snoeyink, J.: Delaunay triangulations of imprecise pointsin linear time after preprocessing. In: Proceedings of 24th Annual Symposium on Computational Geometry, pp. 298\u2013304 (2008)","DOI":"10.1145\/1377676.1377727"},{"issue":"4","key":"195_CR25","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.comgeo.2009.03.007","volume":"43","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.J.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. Theory Appl. 43(4), 419\u2013433 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"195_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1090\/dimacs\/006\/14","volume-title":"Computational Geometry: Papers from the DIMACS Special Year","author":"J Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Computing the center of planar point sets. In: Goodman, J.E., Pollack, R., Steiger, W. (eds.) Computational Geometry: Papers from the DIMACS Special Year, pp. 221\u2013230. Amer. Math. Soc., Providence (1991)"},{"issue":"3","key":"195_CR27","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1006\/jagm.1993.1023","volume":"14","author":"J Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Linear optimization queries. J. Algorithms 14(3), 432\u2013448 (1993)","journal-title":"J. Algorithms"},{"key":"195_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"195_CR29","doi-asserted-by":"crossref","unstructured":"Nagai, T., Tokura, N.: Tight error bounds of geometric problems on convex objects with imprecise coordinates. In: Proceedings of Japanese Conference on Discrete Computational Geometry, pp. 252\u2013263 (2000)","DOI":"10.1007\/3-540-47738-1_24"},{"key":"195_CR30","doi-asserted-by":"crossref","unstructured":"Nagai, T., Yasutome, S., Tokura, N.: Convex hull problem with imprecise input. In: Proceedings of Japanese Conference on Discrete Computational Geometry, pp. 207\u2013219 (1998)","DOI":"10.1007\/978-3-540-46515-7_18"},{"key":"195_CR31","unstructured":"P\u00e9rez-Lantero, P.: Area and perimeter of the convex hull of stochastic points. CoRR \n                    arXiv:1412.5153\n                    \n                   (2014)"},{"key":"195_CR32","unstructured":"Phillips, J.M.: Small and stable descriptors of distributions for geometric statistical problems. Ph.D. Thesis, Department of Computer Science, Duke University (2009)"},{"key":"195_CR33","first-page":"495","volume-title":"Handbook of Discrete and Computational Geometry","author":"R Seidel","year":"2004","unstructured":"Seidel, R.: Convex hull computations. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 495\u2013512. CRC Press, Boca Raton (2004)"},{"key":"195_CR34","unstructured":"Sember, J.: Guarantees concerning geometric objects with uncertain imputs. Ph.D. Thesis, Department of Computer Science, University of British Columbia (2011)"},{"key":"195_CR35","doi-asserted-by":"crossref","unstructured":"Suri, S., Verbeek, K., Yildiz, H.: On the most likely convex hull of uncertain points. In: Proceedings of 21st Annual European Symposium on Algorithms, pp. 791\u2013802 (2013)","DOI":"10.1007\/978-3-642-40450-4_67"},{"issue":"4","key":"195_CR36","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.jda.2008.04.002","volume":"6","author":"MJ van Kreveld","year":"2008","unstructured":"van Kreveld, M.J., L\u00f6ffler, M.: Approximating largest convex hulls for imprecise points. J. Discrete Algorithms 6(4), 583\u2013594 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"195_CR37","unstructured":"Wang, H., Zhang, W.: The $$\\tau $$-skyline for uncertain data. In: Proceedings of 26th Canadian Conference on Computational Geometry, pp. 326\u2013331 (2014)"},{"key":"195_CR38","unstructured":"Zhang, W.: Geometric computing over uncertain data. Ph.D. Thesis, Department of Computer Science, Duke University (2015)"},{"key":"195_CR39","doi-asserted-by":"crossref","unstructured":"Zhao, Z., Yan, D., Ng, W.: A probabilistic convex hull query tool. In: Proceedings of 15th International Conferences on Extending Database Technology, pp. 570\u2013573 (2012)","DOI":"10.1145\/2247596.2247668"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0195-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0195-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0195-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0195-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:21:27Z","timestamp":1589696487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0195-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,15]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["195"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0195-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,15]]},"assertion":[{"value":"26 March 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}