Computing a convex skull of an orthogonal polygon

Derick Wood, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages311-315
Number of pages5
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

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

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/7/85

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Computing a convex skull of an orthogonal polygon'. Together they form a unique fingerprint.

Cite this