Share This Article:

A Gradient Search Algorithm for the Maximal Visible Area Polygon Problem

Abstract Full-Text HTML XML Download Download as PDF (Size:603KB) PP. 168-178
DOI: 10.4236/ajor.2015.53013    2,294 Downloads   2,711 Views  

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 .

Conflicts of Interest

The authors declare no conflicts of interest.

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

  
comments powered by Disqus

Copyright © 2019 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.