Complexity, convexity, and unimodality

Research output: Contribution to journalArticle

Abstract

A class of polygons termed unimodal is introduced. Let P = P1, p2,..., pnbe a simple n-vertex polygon. Given a fixed vertex or edge, several definitions of the distance between the fixed vertex or edge and any other vertex or edge are considered. For a fixed vertex (edge), a distance measure defines a distance function as the remaining vertices (edges) are traversed in order. If for every vertex (edge) of P a specified distance function is unimodal then P is a unimodal polygon in the corresponding sense. Relationships between unimodal polygons, in several senses, and convex polygons are established. Several properties are derived for unimodal polygons when the distance measure is the euclidean distance between vertices of the polygons. These properties lead to very simple 0(n) algorithms for solving a variety of problems that occur in computational geometry and pattern recognition. Furthermore, these algorithms establish that convexity is not the key factor in obtaining linear-time-complexity for solving these problems. The paper closes with several open questions in this area.

Original languageEnglish (US)
Pages (from-to)197-217
Number of pages21
JournalInternational Journal of Computer & Information Sciences
Volume13
Issue number3
DOIs
StatePublished - Jun 1 1984

    Fingerprint

Keywords

  • Unimodality
  • algorithms
  • all-furthest-neighbor problem
  • all-nearest-neighbor problem
  • artificial intelligence
  • closer-pair problem
  • computational geometry
  • convexity
  • diameter
  • geometric complexity
  • pattern recognition
  • polygons

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Cite this