A polynomial solution for the potato-peeling problem

J. S. Chang; C. K. Yap

doi:10.1007/BF02187692

A polynomial solution for the potato-peeling problem

J. S. Chang, C. K. Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English (US)
Pages (from-to)	155-182
Number of pages	28
Journal	Discrete & Computational Geometry
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF02187692
State	Published - Dec 1986

ASJC Scopus subject areas

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

Access to Document

10.1007/BF02187692

Cite this

@article{23dd41e825d742d99041b1773b051743,

title = "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 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.",

author = "Chang, {J. S.} and Yap, {C. K.}",

year = "1986",

month = dec,

doi = "10.1007/BF02187692",

language = "English (US)",

volume = "1",

pages = "155--182",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - A polynomial solution for the potato-peeling problem

AU - Chang, J. S.

AU - Yap, C. K.

PY - 1986/12

Y1 - 1986/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0010423824&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0010423824&partnerID=8YFLogxK

U2 - 10.1007/BF02187692

DO - 10.1007/BF02187692

M3 - Article

AN - SCOPUS:0010423824

SN - 0179-5376

VL - 1

SP - 155

EP - 182

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

A polynomial solution for the potato-peeling problem

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this