Art Gallery Problems for Convex Nested Polygons
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Joyendu Bhadury, Professor, Information Systems and Supply Chain Management (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
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.
Art Gallery Problems for Convex Nested Polygons
PDF (Portable Document Format)
1481 KB
Created on 6/8/2011
Views: 2082
Additional Information
- Publication
- INFORMS Journal on Computing Vol. 9, No. 1, Winter 1997
- Language: English
- Date: 1997
- Keywords
- Algorithms, Polygons, Geometry, Computers