In this article, we study a class of Art Gallery problems that are defined on a pair of convex nested polygons. Polynomial time algorithms are presented for all these problems, by reducing them to the Circle Covering problem, or by relating them to the Minimal Nested Polygon problem. Then it is shown that these problems can also be solved in polynomial time by formulating them as Integer Programs with the Circular Ones property. Finally the paper discusses how these algorithms can be efficiently implemented in parallel.

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. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.