TY - GEN

T1 - Computing a convex skull of an orthogonal polygon

AU - Wood, Derick

AU - Yap, Chee K.

N1 - Publisher Copyright:
© 1985 ACM.

PY - 1985/6/1

Y1 - 1985/6/1

N2 - Given a simple orthogonal polygon, that is a simple polygon whose edges are parallel to the axes, we wish to determine an inscribed convex orthogonal polygon of maximal area. This is the orthogonal version of the potato peeling problem. We present an 0(n2) time algorithm to solve it, which is a substantial improvement over the 0(/i7) time algorithm for the general problem.

AB - Given a simple orthogonal polygon, that is a simple polygon whose edges are parallel to the axes, we wish to determine an inscribed convex orthogonal polygon of maximal area. This is the orthogonal version of the potato peeling problem. We present an 0(n2) time algorithm to solve it, which is a substantial improvement over the 0(/i7) time algorithm for the general problem.

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

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

U2 - 10.1145/323233.323273

DO - 10.1145/323233.323273

M3 - Conference contribution

AN - SCOPUS:84915875552

T3 - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

SP - 311

EP - 315

BT - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

PB - Association for Computing Machinery, Inc

T2 - 1st Annual Symposium on Computational Geometry, SCG 1985

Y2 - 5 June 1985 through 7 June 1985

ER -