Peeling Potatoes Near-Optimally in Near-Linear Time

Abstrakt

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 O((n/epsilon^6) log_2 n log(1/delta)) time we find a convex polygon contained in P that, with probability at least 1 - delta, has area at least (1- epsilon) times the area of an optimal solution.

Klíčová slova

• Geometric optimization
• potato peeling
• visibility graph
• geometric probability
• approximation algorithm