Author(s)

Helman I. Stern¹, Moshe Zofi^1,2

¹Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beersheva, Israel.
²Department of Industrial Management, Sapir College, Sderot, Israel.

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 .

Maximal Visible Polygon, Gradient Search, Continuous Optimization, Guardhouse Problem

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.