{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:36:06Z","timestamp":1783438566834,"version":"3.54.6"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T00:00:00Z","timestamp":1645488000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T00:00:00Z","timestamp":1645488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0297"],"award-info":[{"award-number":["P1-0297"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-8130"],"award-info":[{"award-number":["J1-8130"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-8155"],"award-info":[{"award-number":["J1-8155"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-9109"],"award-info":[{"award-number":["J1-9109"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-1693"],"award-info":[{"award-number":["J1-1693"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814026"],"award-info":[{"award-number":["CCF-1814026"]}],"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":[[2022,4]]},"DOI":"10.1007\/s00454-021-00368-3","type":"journal-article","created":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T15:02:51Z","timestamp":1645542171000},"page":"843-881","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing Shapley Values in the Plane"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3183-4126","authenticated-orcid":false,"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,2,22]]},"reference":[{"issue":"2","key":"368_CR1","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/s00453-016-0195-y","volume":"79","author":"PK Agarwal","year":"2017","unstructured":"Agarwal, P.K., Har-Peled, S., Suri, S., Yildiz, H., Zhang, W.: Convex hulls under uncertainty. Algorithmica 79(2), 340\u2013367 (2017)","journal-title":"Algorithmica"},{"key":"368_CR2","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.jcss.2017.09.006","volume":"94","author":"PK Agarwal","year":"2018","unstructured":"Agarwal, P.K., Kumar, N., Sintos, S., Suri, S.: Range-max queries on uncertain data. J. Comput. Syst. Sci. 94, 118\u2013134 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"368_CR3","doi-asserted-by":"crossref","unstructured":"Ajwani, D., Ray, S., Seidel, R., Tiwary, H.R.: On computing the centroid of the vertices of an arrangement and related problems. In: 10th International Workshop on Algorithms and Data Structures (Halifax 2007). Lecture Notes in Comput. Sci., vol. 4619, pp. 519\u2013528. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-73951-7_45"},{"issue":"3","key":"368_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s13160-012-0078-9","volume":"29","author":"K Ando","year":"2012","unstructured":"Ando, K.: Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases. Jpn. J. Ind. Appl. Math. 29(3), 385\u2013400 (2012)","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"368_CR5","doi-asserted-by":"crossref","unstructured":"Aronov, B., Katz, M.J.: Batched point location in SINR diagrams via algebraic tools. ACM Trans. Algorithms 14(4), #\u00a041 (2018)","DOI":"10.1145\/3209678"},{"key":"368_CR6","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"368_CR7","unstructured":"Cabello, S., Chan, T.M.: Computing Shapley values in the plane. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz International Proceedings in Informatics, vol. 129, #\u00a020. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"368_CR8","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 16. Morgan & Claypool, Williston (2012)","DOI":"10.1007\/978-3-031-01558-8"},{"key":"368_CR9","doi-asserted-by":"crossref","unstructured":"Deng, X., Fang, Q.: Algorithmic cooperative game theory. In: Pareto Optimality, Game Theory and Equilibria. Springer Optimization and Its Applications, vol. 17, pp. 159\u2013185. Springer, New York (2008)","DOI":"10.1007\/978-0-387-77247-9_7"},{"issue":"2","key":"368_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.19.2.257","volume":"19","author":"X Deng","year":"1994","unstructured":"Deng, X., Papadimitriou, Ch.H.: On the complexity of cooperative solution concepts. Math. Oper. Res. 19(2), 257\u2013266 (1994)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"368_CR11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"368_CR12","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H Edelsbrunner","year":"1993","unstructured":"Edelsbrunner, H., Seidel, R., Sharir, M.: On the zone theorem for hyperplane arrangements. SIAM J. Comput. 22(2), 418\u2013429 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"368_CR13","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01545526","volume":"20","author":"U Faigle","year":"1998","unstructured":"Faigle, U., Fekete, S.P., Hochst\u00e4ttler, W., Kern, W.: On approximately fair cost allocation in Euclidean TSP games. OR Spektrum 20(1), 29\u201337 (1998)","journal-title":"OR Spektrum"},{"issue":"3","key":"368_CR14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF01263277","volume":"26","author":"U Faigle","year":"1997","unstructured":"Faigle, U., Kern, W., Fekete, S.P., Hochst\u00e4ttler, W.: On the complexity of testing membership in the core of min-cost spanning tree games. Int. J. Game Theory 26(3), 361\u2013366 (1997)","journal-title":"Int. J. Game Theory"},{"key":"368_CR15","doi-asserted-by":"publisher","DOI":"10.1142\/10634","volume-title":"A Course in Game Theory","author":"TS Ferguson","year":"2020","unstructured":"Ferguson, T.S.: A Course in Game Theory. World Scientific, Hackensack (2020)"},{"issue":"2","key":"368_CR16","first-page":"32","volume":"8","author":"M Fink","year":"2017","unstructured":"Fink, M., Hershberger, J., Kumar, N., Suri, S.: Hyperplane separability and convexity of probabilistic point sets. J. Comput. Geom. 8(2), 32\u201357 (2017)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"368_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01584227","volume":"21","author":"D Granot","year":"1981","unstructured":"Granot, D., Huberman, G.: Minimum cost spanning tree games. Math. Program. 21(1), 1\u201318 (1981)","journal-title":"Math. Program."},{"key":"368_CR18","doi-asserted-by":"crossref","unstructured":"Kamousi, P., Chan, T.M., Suri, S.: Stochastic minimum spanning trees in Euclidean spaces. In: 27th Annual Symposium on Computational Geometry (Paris 2011), pp. 65\u201374. ACM, New York (2011)","DOI":"10.1145\/1998196.1998206"},{"issue":"2B","key":"368_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.M., Suri, S.: Closest pair and the post office problem for stochastic points. Comput. Geom. 47(2B), 214\u2013223 (2014)","journal-title":"Comput. Geom."},{"issue":"4","key":"368_CR20","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/s00454-003-2856-2","volume":"30","author":"S Langerman","year":"2003","unstructured":"Langerman, S.: The complexity of halfspace area queries. Discrete Comput. Geom. 30(4), 639\u2013648 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"368_CR21","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1287\/mnsc.20.3.370","volume":"20","author":"SC Littlechild","year":"1973","unstructured":"Littlechild, S.C., Owen, G.: A simple expression for the Shapely value in a special case. Manag. Sci. 20(3), 370\u2013372 (1973)","journal-title":"Manag. Sci."},{"key":"368_CR22","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)","DOI":"10.1007\/978-1-4613-0039-7"},{"issue":"3","key":"368_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1287\/moor.3.3.189","volume":"3","author":"N Megiddo","year":"1978","unstructured":"Megiddo, N.: Computational complexity of the game theory approach to cost allocation for a tree. Math. Oper. Res. 3(3), 189\u2013196 (1978)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"368_CR24","doi-asserted-by":"publisher","first-page":"# 3","DOI":"10.1145\/2847257","volume":"12","author":"G Moroz","year":"2016","unstructured":"Moroz, G., Aronov, B.: Computing the distance between piecewise-linear bivariate functions. ACM Trans. Algorithms 12(1), # 3 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"368_CR25","volume-title":"Game Theory: Analysis of Conflict","author":"RB Myerson","year":"1997","unstructured":"Myerson, R.B.: Game Theory: Analysis of Conflict. Harvard University Press, Cambridge (1997)"},{"key":"368_CR26","volume-title":"Algorithmic Game Theory","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V.V. (eds.): Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)"},{"key":"368_CR27","volume-title":"A Course in Game Theory","author":"MJ Osborne","year":"1994","unstructured":"Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)"},{"issue":"6","key":"368_CR28","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1137\/0220065","volume":"20","author":"MH Overmars","year":"1991","unstructured":"Overmars, M.H., Yap, C.-K.: New upper bounds in Klee\u2019s measure problem. SIAM J. Comput. 20(6), 1034\u20131045 (1991)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"368_CR29","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1093\/comjnl\/bxv124","volume":"59","author":"P P\u00e9rez-Lantero","year":"2016","unstructured":"P\u00e9rez-Lantero, P.: Area and perimeter of the convex hull of stochastic points. Comput. J. 59(8), 1144\u20131154 (2016)","journal-title":"Comput. J."},{"issue":"2","key":"368_CR30","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/j.ejor.2011.04.020","volume":"214","author":"J Puerto","year":"2011","unstructured":"Puerto, J., Tamir, A., Perea, F.: A cooperative location game based on the 1-center location problem. Eur. J. Oper. Res. 214(2), 317\u2013330 (2011)","journal-title":"Eur. J. Oper. Res."},{"issue":"7\u20138","key":"368_CR31","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1016\/j.dam.2011.07.020","volume":"160","author":"J Puerto","year":"2012","unstructured":"Puerto, J., Tamir, A., Perea, F.: Cooperative location games based on the minimum diameter spanning Steiner subgraph problem. Discrete Appl. Math. 160(7\u20138), 970\u2013979 (2012)","journal-title":"Discrete Appl. Math."},{"key":"368_CR32","doi-asserted-by":"crossref","unstructured":"Roth, A.E. (ed.): The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press, Cambridge (1988)","DOI":"10.1017\/CBO9780511528446"},{"key":"368_CR33","unstructured":"Thomson, W.: Cost allocation and airport problems (2014). https:\/\/www.iser.osaka-u.ac.jp\/collabo\/20140524\/Airport_Problems.pdf"},{"key":"368_CR34","doi-asserted-by":"crossref","unstructured":"Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: New Results and New Trends in Computer Science (Graz 1991). Lecture Notes in Comput. Sci., vol. 555, pp. 359\u2013370. Springer, Berlin (1991)","DOI":"10.1007\/BFb0038202"},{"issue":"1","key":"368_CR35","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1137\/0214019","volume":"14","author":"DE Willard","year":"1985","unstructured":"Willard, D.E.: New data structures for orthogonal range queries. SIAM J. Comput. 14(1), 232\u2013253 (1985)","journal-title":"SIAM J. Comput."},{"key":"368_CR36","doi-asserted-by":"crossref","unstructured":"Winter, E.: The Shapley value. In: Handbook of Game Theory with Economic Applications, vol. 3, pp. 2025\u20132054. North-Holland, Amsterdam (2002)","DOI":"10.1016\/S1574-0005(02)03016-3"},{"key":"368_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2018.06.001","volume":"74","author":"J Xue","year":"2018","unstructured":"Xue, J., Li, Y., Janardan, R.: On the separability of stochastic geometric objects, with applications. Comput. Geom. 74, 1\u201320 (2018)","journal-title":"Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00368-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00368-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00368-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T17:59:56Z","timestamp":1674842396000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00368-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,22]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["368"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00368-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,22]]},"assertion":[{"value":"3 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}