Peeling potatoes near-optimally in near-linear time

Sergio Cabello, Josef Cibulka, Jan Kynčl +2

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…