The orthogonal convex skull problem

Derick Wood, Chee K. Yap

Research output: Contribution to journalArticle

Abstract

We give a combinatorial definition of the notion of a simple orthogonal polygon being k-concave, where k is a nonnegative integer. (A polygon is orthogonal if its edges are only horizontal or vertical.) Under this definition an orthogonal polygon which is 0-concave is convex, that is, it is a rectangle, and one that is 1-concave is orthoconvex in the usual sense, and vice versa. Then we consider the problem of computing an orthoconvex orthogonal polygon of maximal area contained in a simple orthogonal polygon. This is the orthogonal version of the potato peeling problem. An O(n2) algorithm is presented, which is a substantial improvement over the O(n7) time algorithm for the general problem.

Original languageEnglish (US)
Pages (from-to)349-365
Number of pages17
JournalDiscrete & Computational Geometry
Volume3
Issue number1
DOIs
StatePublished - Dec 1988

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'The orthogonal convex skull problem'. Together they form a unique fingerprint.

  • Cite this