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.
[2] Stern, H. (1989) Polygonal Entropy: A Convexity Measure. Pattern Recognition Letters, 10, 229-235.
[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.
[6] Lee, D.T. and Lin, A.K. (1986) Computational Complexity of Art Gallery Problems. IEEE Transactions on Information Theory, 32, 276-282.

Copyright © 2022 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.