AJOR  Vol.5 No.3 , May 2015
A Gradient Search Algorithm for the Maximal Visible Area Polygon Problem
Author(s) Helman I. Stern1, Moshe Zofi1,2
ABSTRACT
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 .

Cite this paper
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.
References
[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

 
 
Top