Art gallery problems for convex nested polygons

Art gallery problems for convex nested polygons

0.00 Avg rating0 Votes
Article ID: iaor19982867
Country: United States
Volume: 9
Issue: 1
Start Page Number: 100
End Page Number: 110
Publication Date: Dec 1997
Journal: INFORMS Journal On Computing
Authors: , , ,
Keywords: programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.