Monotone pieces of chains

Chandru, V. ; Rajan, V. T. ; Swaminathan, R. (1992) Monotone pieces of chains ORSA Journal on Computing, 4 (4). pp. 439-446. ISSN 0899-1499

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Operations Research Society of America.
Keywords:Analysis of Algorithms: Computational Complexity; Polygon; Decomposition
ID Code:5543
Deposited On:19 Oct 2010 11:57
Last Modified:28 May 2011 07:12

Repository Staff Only: item control page