Complexity, convexity, and unimodality

A class of polygons termed unimodal is introduced. Let P = P₁, p₂,..., p_nbe 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.