TY - GEN
T1 - A polynomial solution for potato-peeling and other polygon inclusion and enclosure problems
AU - Chang, J. S.
AU - Yap, C. K.
N1 - Funding Information:
‘Work in this paper has km s y p t e d in part by NSF grants #IXlW$+ 01898 and UDCR-84-01633, the Office of Yaval Research Grant NW14-82-X-
Publisher Copyright:
© 1984 IEEE.
PY - 1984
Y1 - 1984
N2 - We give a finiteness criteria for the potato-peeling problem that asks for the largest convex polygon ('potato') contained inside a given simple polygon, answering a question of J. Goodman. This leads to a polynomial-time solution of O(n9g n). The techniques used turn out to be useful for other cases of what we call the polygon inclusion and enclosure problems. For instance, the largest perimeter potato can be found in O(n6) time and finding the smallest k-gon enclosing a given polygon can be done in O(n3log k) steps.
AB - We give a finiteness criteria for the potato-peeling problem that asks for the largest convex polygon ('potato') contained inside a given simple polygon, answering a question of J. Goodman. This leads to a polynomial-time solution of O(n9g n). The techniques used turn out to be useful for other cases of what we call the polygon inclusion and enclosure problems. For instance, the largest perimeter potato can be found in O(n6) time and finding the smallest k-gon enclosing a given polygon can be done in O(n3log k) steps.
UR - http://www.scopus.com/inward/record.url?scp=85115202707&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115202707&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85115202707
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 408
EP - 416
BT - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PB - IEEE Computer Society
T2 - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Y2 - 24 October 1984 through 26 October 1984
ER -