Lecture by Sergio Cabello (Universität Ljubljana): Computational geometry, optimization and Shapley values

Feb 11, 2019 | 02:15 PM

I will discuss three unrelated sets of results combining geometry and algorithms. First we will see classes of graphs defined using the intersection of geometric objects in the plane, and discuss classical optimization problems for them. Then we will consider approximation algorithms for the potato peeling problem: find a maximum-area convex body inside a given polygon. The problem amounts to finding a maximum clique in the visibility graph of random samples of points inside the polygon, and results from stochastic geometry are used to bound the size of the samples. Finally, we will discuss the efficient computation of Shapley values for coalitional games defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box.

Time & Location

Feb 11, 2019 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)