Computing a convex skull of an orthogonal polygon

Derick Wood; Chee K. Yap

doi:10.1145/323233.323273

Computing a convex skull of an orthogonal polygon

Derick Wood, Chee K. Yap

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
Publisher	Association for Computing Machinery, Inc
Pages	311-315
Number of pages	5
ISBN (Electronic)	0897911636, 9780897911634
DOIs	https://doi.org/10.1145/323233.323273
State	Published - Jun 1 1985
Event	1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States Duration: Jun 5 1985 → Jun 7 1985

Publication series

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

Other

Other	1st Annual Symposium on Computational Geometry, SCG 1985
Country/Territory	United States
City	Baltimore
Period	6/5/85 → 6/7/85

ASJC Scopus subject areas

Computational Mathematics
Geometry and Topology

Access to Document

10.1145/323233.323273

Cite this

Computing a convex skull of an orthogonal polygon. / Wood, Derick; Yap, Chee K.
Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985. Association for Computing Machinery, Inc, 1985. p. 311-315 (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Wood, D & Yap, CK 1985, Computing a convex skull of an orthogonal polygon. in Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985. Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985, Association for Computing Machinery, Inc, pp. 311-315, 1st Annual Symposium on Computational Geometry, SCG 1985, Baltimore, United States, 6/5/85. https://doi.org/10.1145/323233.323273

@inproceedings{5cdcab7e6c4c4f3fa2f9bb8ef8ee2743,

title = "Computing a convex skull of an orthogonal polygon",

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

author = "Derick Wood and Yap, {Chee K.}",

note = "Publisher Copyright: {\textcopyright} 1985 ACM.; 1st Annual Symposium on Computational Geometry, SCG 1985 ; Conference date: 05-06-1985 Through 07-06-1985",

year = "1985",

month = jun,

day = "1",

doi = "10.1145/323233.323273",

language = "English (US)",

series = "Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985",

publisher = "Association for Computing Machinery, Inc",

pages = "311--315",

booktitle = "Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985",

}

TY - GEN

T1 - Computing a convex skull of an orthogonal polygon

AU - Wood, Derick

AU - Yap, Chee K.

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 -

Computing a convex skull of an orthogonal polygon

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this