TY - JOUR

T1 - Computing Shapley Values in the Plane

AU - Cabello, Sergio

AU - Chan, Timothy M.

N1 - Funding Information:
S. Cabello: supported by the Slovenian Research Agency, program P1-0297 and projects J1-8130, J1-8155, J1-9109, J1-1693. T. M. Chan: supported in part by NSF Grant CCF-1814026.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022/4

Y1 - 2022/4

N2 - We consider the problem of computing Shapley values for points in the plane, where each point is interpreted as a player, and the value of a coalition is defined by the area or the perimeter of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box. For sets of n points in the plane, we show how to compute in roughly O(n3 / 2) time the Shapley values for the area of the minimum axis-parallel bounding box and the area of the union of the rectangles spanned by the origin and the input points. When the points form an increasing or decreasing chain, the running time can be improved to near-linear. In all these cases, we use linearity of the Shapley values and algebraic methods. We also show that Shapley values for the area and the perimeter of the convex hull can be computed in O(n2) time, while for the minimum enclosing disk it takes O(n3) time. These problems are closely related to the model of stochastic point sets considered in computational geometry, but here we have to consider random insertion orders of the points instead of a probabilistic existence of points.

AB - We consider the problem of computing Shapley values for points in the plane, where each point is interpreted as a player, and the value of a coalition is defined by the area or the perimeter of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box. For sets of n points in the plane, we show how to compute in roughly O(n3 / 2) time the Shapley values for the area of the minimum axis-parallel bounding box and the area of the union of the rectangles spanned by the origin and the input points. When the points form an increasing or decreasing chain, the running time can be improved to near-linear. In all these cases, we use linearity of the Shapley values and algebraic methods. We also show that Shapley values for the area and the perimeter of the convex hull can be computed in O(n2) time, while for the minimum enclosing disk it takes O(n3) time. These problems are closely related to the model of stochastic point sets considered in computational geometry, but here we have to consider random insertion orders of the points instead of a probabilistic existence of points.

KW - Airport problem

KW - Arrangements

KW - Bounding box

KW - Convex hull

KW - Convolutions

KW - Minimum enclosing disk

KW - Shapley values

KW - Stochastic computational geometry

UR - http://www.scopus.com/inward/record.url?scp=85124958030&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85124958030&partnerID=8YFLogxK

U2 - 10.1007/s00454-021-00368-3

DO - 10.1007/s00454-021-00368-3

M3 - Article

AN - SCOPUS:85124958030

SN - 0179-5376

VL - 67

SP - 843

EP - 881

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -