A polynomial solution for the potato-peeling problem

J. S. Chang, C. K. Yap

Research output: Contribution to journalArticle

Abstract

The potato-peeling problem asks for the largest convex polygon contained inside a given simple polygon. We give an O(n7) time algorithm to this problem, answering a question of Goodman. We also give an O(n6) time algorithm if the desired polygon is maximized with respect to perimeter.

Original languageEnglish (US)
Pages (from-to)155-182
Number of pages28
JournalDiscrete & Computational Geometry
Volume1
Issue number1
DOIs
StatePublished - Dec 1986

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A polynomial solution for the potato-peeling problem'. Together they form a unique fingerprint.

  • Cite this