Browse All

Theses & Dissertations

Submissions

  • Submissions (Articles, Chapters, and other finished products)

Art Gallery Problems for Convex Nested Polygons

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Joyendu Bhadury, Associate Dean - Graduate Programs and Research (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.

Additional Information

Publication
INFORMS Journal on Computing Vol. 9, No. 1, Winter 1997
Language: English
Date: 1997
Keywords
Algorithms, Polygons, Geometry, Computers