TITLE:
A Gradient Search Algorithm for the Maximal Visible Area Polygon Problem
AUTHORS:
Helman I. Stern, Moshe Zofi
KEYWORDS:
Maximal Visible Polygon, Gradient Search, Continuous Optimization, Guardhouse Problem
JOURNAL NAME:
American Journal of Operations Research,
Vol.5 No.3,
May
12,
2015
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 .