A Gradient Search Algorithm for the Maximal Visible Area Polygon Problem

This paper provides a gradient search algorithm for finding the maximal visible area polygon (VAP) viewed by an interior point in a simple polygon P. The algorithm is based on a natural partition of P into convex sets, such that each element of the partition is associated with a unique analytical form of the area function. We call this partition a back diagonal partition of P. Our maximal VAP algorithm converges in a finite number of steps, and is polynomial with a complexity of , for a simple polygon P with n vertices, and r reflex vertices. We use the maximal VAP algorithm as a basis for a greedy heuristic for the well known guardhouse problem with a computation complexity of .

Share and Cite:

Stern, H. and Zofi, M. (2015) A Gradient Search Algorithm for the Maximal Visible Area Polygon Problem. American Journal of Operations Research, 5, 168-178. doi: 10.4236/ajor.2015.53013.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] El Gindy, H. and Davis, D. (1981) A Linear Algorithm for Computing the Visible Polygon from a Point. Journal of Algorithms, 2, 186-197. http://dx.doi.org/10.1016/0196-6774(81)90019-5 [2] Stern, H. (1989) Polygonal Entropy: A Convexity Measure. Pattern Recognition Letters, 10, 229-235. http://dx.doi.org/10.1016/0167-8655(89)90093-7 [3] Cheong, O., Efrat, A. and Har-Peled, S. (2004) On Finding a Guard That Sees Most and a Shop That Sells Most. Proc. 15th ACM-SIAM Sympos. Discrete Algorithms 1098-1107. [4] O’Rourke, J. (1987) Art Gallery Theorems and Algorithms. Oxford University Press, Oxford. [5] Amit, Y., Mitchell, J.S.B. and Packer, E. (2010) Locating Guards for Visibility Coverage of Polygons. International Journal of Computational Geometry & Applications, 20, 601-630. http://dx.doi.org/10.1142/S0218195910003451 [6] Lee, D.T. and Lin, A.K. (1986) Computational Complexity of Art Gallery Problems. IEEE Transactions on Information Theory, 32, 276-282. http://dx.doi.org/10.1109/TIT.1986.1057165