Bhadury, J. ; Chandru, V. ; Maheshwari, A. ; Chandrasekaran, R. (1997) Art gallery problems for convex nested polygons Informs Journal on Computing, 9 (1). pp. 100-110. ISSN 1091-9856
Full text not available from this repository.
Official URL: http://joc.journal.informs.org/cgi/content/abstrac...
Related URL: http://dx.doi.org/10.1287/ijoc.9.1.100
Abstract
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Institute for Operations Research and the Management Sciences. |
| Keywords: | Computer Science; Computational Geometry; Art Gallery Problems; Convex Polygons |
| ID Code: | 5546 |
| Deposited On: | 19 Oct 2010 11:57 |
| Last Modified: | 28 May 2011 07:18 |
Repository Staff Only: item control page
