Peeling potatoes near-optimally in near-linear time
Decanato - Facoltà di scienze informatiche
Data d'inizio: 10 Ottobre 2014
Data di fine: 11 Ottobre 2014
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
ABSTRACT:
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.
BIO:
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
