Seminars at the Faculty of Informatics

Peeling potatoes near-optimally in near-linear time

The Faculty of Informatics is pleased to announce a seminar given by Maria Saumell

DATE: Friday, October 10th, 2014
PLACE: USI Lugano campus, SI-006, Informatics building (Via G. Buffi 13)
TIME: 15:30

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near linear time (1-epsilon)-approximation algorithm for this problem: in sub quadratic time, we find a convex polygon contained in P that, with high probability, has area at least (1-epsilon) times the area of an optimal solution.

Maria Saumell is a postdoctoral researcher at University of West Bohemia in Pilsen. Her area of expertise is Combinatorial and Computational Geometry. She obtained her PhD at Universitat Politčcnica de Catalunya in 2011.

HOST: Prof. Evanthia Papadopoulou