License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.20
URN: urn:nbn:de:0030-drops-104244
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10424/
Go to the corresponding LIPIcs Volume Portal

Cabello, Sergio ; Chan, Timothy M.

Computing Shapley Values in the Plane

pdf-format:
LIPIcs-SoCG-2019-20.pdf (1 MB)

Abstract

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 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(n^{3/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 of the convex hull or the minimum enclosing disk can be computed in O(n^2) and O(n^3) time, respectively. 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.

BibTeX - Entry

@InProceedings{cabello_et_al:LIPIcs:2019:10424,
  author =	{Sergio Cabello and Timothy M. Chan},
  title =	{{Computing Shapley Values in the Plane}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10424},
  URN =		{urn:nbn:de:0030-drops-104244},
  doi =		{10.4230/LIPIcs.SoCG.2019.20},
  annote =	{Keywords: Shapley values, stochastic computational geometry, convex hull, minimum enclosing disk, bounding box, arrangements, convolutions, airport problem}
}

Keywords: Shapley values, stochastic computational geometry, convex hull, minimum enclosing disk, bounding box, arrangements, convolutions, airport problem
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI