A polynomial solution for the potato-peeling problem

摘要

[[abstract]]The potato-peeling problem asks for the largest convex polygon contained inside a given simple polygon. We give anO(n 7) time algorithm to this problem, answering a question of Goodman. We also give anO(n 6) time algorithm if the desired polygon is maximized with respect to perimeter.Work in this paper has been supported in part by NSF grants #DCR-84-01898 and #DCR-84-01633, the Office of Naval Research Grant N00014-82-K-0381, and by grants from Digital Equipment Corporation, the Sloan Foundation, the System Development Foundation, and the IBM Corporation. This paper contains the main results of the paper A Polynomial Solution for Potato-Peeling and other Polygon Inclusion and Enclosure Problems presented in the 25th Foundation of Computer Science Conference, 1984, Florida. The second half of that paper is submitted for publication elsewhere [1].