{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:56Z","timestamp":1740109616270,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T00:00:00Z","timestamp":1470009600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T00:00:00Z","timestamp":1470009600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1421231, CCF-1217462","CCF-1421231, CCF-1217462"],"award-info":[{"award-number":["CCF-1421231, CCF-1217462","CCF-1421231, CCF-1217462"]}],"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-1421231, CCF-1217462"],"award-info":[{"award-number":["CCF-1421231, CCF-1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00454-016-9808-0","type":"journal-article","created":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T13:27:15Z","timestamp":1470058035000},"page":"631-656","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["From Proximity to Utility: A Voronoi Partition of Pareto Optima"],"prefix":"10.1007","volume":"56","author":[{"given":"Hsien-Chih","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,1]]},"reference":[{"key":"9808_CR1","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Schwarzkopf, O.: Computing many faces in arrangements of lines and segments. SIAM J. Comput. 27(2), 491\u2013505 (1998). \n                    http:\/\/epubs.siam.org\/sam-bin\/dbq\/article\/26616"},{"issue":"3","key":"9808_CR2","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s00454-014-9626-1","volume":"52","author":"PK Agarwal","year":"2014","unstructured":"Agarwal, P.K., Har-Peled, S., Kaplan, H., Sharir, M.: Union of random Minkowski sums and network vulnerability analysis. Discrete Comput. Geom. 52(3), 551\u2013582 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"9808_CR3","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 the 32nd ACM Symposium on Principles of Database Systems (PODS), pp. 115\u2013126 (2013)","DOI":"10.1145\/2463664.2465219"},{"key":"9808_CR4","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)"},{"key":"9808_CR5","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1142\/S0218195992000214","volume":"2","author":"F Aurenhammer","year":"1992","unstructured":"Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Int. J. Comput. Geom. Appl. 2, 363\u2013381 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9808_CR6","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1002\/rsa.20053","volume":"27","author":"Z Bai","year":"2005","unstructured":"Bai, Z., Devroye, L., Hwang, H., Tsai, T.: Maxima in hypercubes. Random Struct. Algorithms 27(3), 290\u2013309 (2005)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"9808_CR7","doi-asserted-by":"publisher","first-page":"1986","DOI":"10.1016\/j.aim.2010.04.012","volume":"225","author":"I B\u00e1r\u00e1ny","year":"2010","unstructured":"B\u00e1r\u00e1ny, I., Reitzner, M.: On the variance of random polytopes. Adv. Math. 225(4), 1986\u20132001 (2010)","journal-title":"Adv. Math."},{"issue":"4","key":"9808_CR8","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.1214\/09-AOP514","volume":"38","author":"I B\u00e1r\u00e1ny","year":"2010","unstructured":"B\u00e1r\u00e1ny, I., Reitzner, M.: Poisson polytopes. Ann. Prob. 38(4), 1507\u20131531 (2010)","journal-title":"Ann. Prob."},{"issue":"4","key":"9808_CR9","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1145\/322092.322095","volume":"25","author":"JL Bentley","year":"1978","unstructured":"Bentley, J.L., Kung, H.T., Schkolnick, M., Thompson, C.D.: On the average number of maxima in a set of vectors and applications. J. Assoc. Comput. Mach. 25(4), 536\u2013543 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9808_CR10","doi-asserted-by":"crossref","unstructured":"Berg, M., Cheong, O., Kreveld, M., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008). \n                    http:\/\/www.cs.uu.nl\/geobook\/","DOI":"10.1007\/978-3-540-77974-2"},{"key":"9808_CR11","unstructured":"B\u00f6rzs\u00f6nyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th IEEE International Conference on Data Engineering, pp. 421\u2013430 (2001). \n                    http:\/\/doi.ieeecomputersociety.org\/10.1109\/ICDE.2001.914855"},{"key":"9808_CR12","doi-asserted-by":"publisher","unstructured":"Chang, H.C., Har-Peled, S., Raichel, B.: From proximity to utility: a Voronoi partition of Pareto optima. In: 31st International Symposium on Computational Geometry (SoCG 2015), vol.\u00a034, pp. 689\u2013703 (2015). doi:\n                    10.4230\/LIPIcs.SOCG.2015.689\n                    \n                  . \n                    http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2015\/5092","DOI":"10.4230\/LIPIcs.SOCG.2015.689"},{"issue":"3","key":"9808_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229\u2013249 (1990)","journal-title":"Combinatorica"},{"key":"9808_CR14","unstructured":"Clarkson, K.L.: On the expected number of $$k$$-sets of coordinate-wise independent points (2004). \n                    http:\/\/cm.bell-labs.com\/who\/clarkson\/cwi_ksets\/p.pdf\n                    \n                  . Manuscript"},{"key":"9808_CR15","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discrete Comput. Geom. 4, 387\u2013421 (1989). \n                    http:\/\/cm.bell-labs.com\/who\/clarkson\/rs2m.html"},{"issue":"4","key":"9808_CR16","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"KL Clarkson","year":"1993","unstructured":"Clarkson, K.L., Mehlhorn, K., Seidel, R.: Four results on randomized incremental constructions. Comput. Geom. Theory Appl. 3(4), 185\u2013212 (1993)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9808_CR17","volume-title":"The New Palgrave Dictionary of Economics","author":"A Feldman","year":"2008","unstructured":"Feldman, A.: Welfare economics. In: Durlauf, S., Blume, L. (eds.) The New Palgrave Dictionary of Economics. Palgrave Macmillan, New York (2008)"},{"issue":"1","key":"9808_CR18","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s00778-006-0029-7","volume":"16","author":"P Godfrey","year":"2007","unstructured":"Godfrey, P., Shipley, R., Gryz, J.: Algorithms and analyses for maximal vector computation. VLDB J. 16(1), 5\u201328 (2007)","journal-title":"VLDB J."},{"key":"9808_CR19","volume-title":"Geometric Approximation Algorithms, Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms, Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Boston (2011)"},{"key":"9808_CR20","doi-asserted-by":"publisher","unstructured":"Har-Peled, S., Raichel, B.: On the expected complexity of randomly weighted Voronoi diagrams. In: Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG), pp. 232\u2013241 (2014). doi:\n                    10.1145\/2582112.2582158","DOI":"10.1145\/2582112.2582158"},{"key":"9808_CR21","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."},{"issue":"2","key":"9808_CR22","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/110856952","volume":"42","author":"H Hwang","year":"2013","unstructured":"Hwang, H., Tsai, T., Chen, W.: Threshold phenomena in $$k$$-dominant skylines of random samples. SIAM J. Comput. 42(2), 405\u2013441 (2013)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9808_CR23","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H Kung","year":"1975","unstructured":"Kung, H., Luccio, F., Preparata, F.: On finding the maxima of a set of vectors. J. Assoc. Comput. Mach. 22(4), 469\u2013476 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"9808_CR24","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0255(84)90025-2","volume":"33","author":"T Ottmann","year":"1984","unstructured":"Ottmann, T., Soisalon-Soininen, E., Wood, D.: On the definition and computation of rectlinear convex hulls. Inf. Sci. 33(3), 157\u2013171 (1984)","journal-title":"Inf. Sci."},{"key":"9808_CR25","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1016\/B978-0-444-89597-4.50022-6","volume-title":"Handbook of Convex Geometry, vol. B, chap. 5.1","author":"R Schneider","year":"1993","unstructured":"Schneider, R., Wieacker, J.A.: Integral geometry. In: Gruber, P.M., Wills, J.M. (eds.) Handbook of Convex Geometry, vol. B, chap. 5.1, pp. 1349\u20131390. North-Holland, Amsterdam (1993)"},{"key":"9808_CR26","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-58043-7_3","volume-title":"New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics","author":"R Seidel","year":"1993","unstructured":"Seidel, R.: Backwards analysis of randomized geometric algorithms. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 10, pp. 37\u201368. Springer, New York (1993)"},{"issue":"2","key":"9808_CR27","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1017\/S0963548302005527","volume":"12","author":"M Sharir","year":"2003","unstructured":"Sharir, M.: The Clarkson\u2013Shor technique revisited and extended. Comb. Prob. Comput. 12(2), 191\u2013201 (2003)","journal-title":"Comb. Prob. Comput."},{"key":"9808_CR28","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995). \n                    http:\/\/us.cambridge.org\/titles\/catalogue.asp?isbn=0521470250"},{"key":"9808_CR29","first-page":"1393","volume-title":"Handbook of Convex Geometry, vol.\u00a0B, chap. 5.2","author":"W Weil","year":"1993","unstructured":"Weil, W., Wieacker, J.A.: Stochastic geometry. In: Gruber, P.M., Wills, J.M. (eds.) Handbook of Convex Geometry, vol.\u00a0B, chap. 5.2, pp. 1393\u20131438. North-Holland, Amsterdam (1993)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9808-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-016-9808-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9808-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9808-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:33:58Z","timestamp":1589697238000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-016-9808-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,1]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["9808"],"URL":"https:\/\/doi.org\/10.1007\/s00454-016-9808-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2016,8,1]]},"assertion":[{"value":"20 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2016","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2016","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}