Monotone pieces of chains

Abstract

The problem of decomposing a general polygonal chain, open or closed, into a minimum number of monotone subchains is studied in this paper. We show that this geometric optimization problem can be solved in linear time (in the number of edges) by a strategy related to the selection of a minimum cardinality cover of a circle by a subset of its arcs. We also introduce a special class of polygonal chains, called stable configurations. These stable configurations are certificates of when a greedy procedure is guaranteed to be optimal for the monotone chain decomposition problem. The greedy procedure translates to a very simple linear-time algorithm. Further, the presence of the stable-configuration-certificate in any given polygonal chain can also be recognized in linear time.