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(log(2) n + (1/epsilon(3)) log n + 1/epsilon(4))) time we find a convex polygon contained in P that, with probability at least 2/3, has area at least (1- epsilon) times the area of an optimal solution.
We also obtain similar results for the variant of computing a convex polygon inside P with maximum perimeter. To achieve these results we provide new results in geometric probability.
The first result is a bound relating the area of the largest convex body inside P to the probability that two points chosen uniformly at random inside P are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body K and the perimeter of the convex hull of a uniform random sample inside K.