Back Diagonal Reflex Algorithm for Finding the Maximal Visual Area Polygon

Abstract

A gradient search algorithm is proffered for finding the maximal visible area polygon (VAP) from an interior point of a simple polygon . The area function over all points  is not well behaved, being in general neither convex nor concave, including points that may be non-differentiable and even discontinuous. The area function  returns the visible area viewed by any point in the polygon . We develop a "back diagonal partition" (BDP) of based on the vision properties of its reflex vertices. Our maximal VAP algorithm is gradient based and converges in a finite number of steps, It has polynomial complexity , for a polygon  with vertices, and reflex vertices. The maximal VAP algorithm is embedded in a heuristic for solving the well-known guardhouse problem which is polynomial with time complexity of . Our main contributions are: (i) A back diagonal reflex (BDR) algorithm which is a noncontinuous gradient VAP algorithm over a BDP domain, (ii) incorporation of this gradient algorithm into a probabilistic heuristic algorithm for finding a point in  which finds an approximate solution to the Max VAP problem, and (iii) an efficient heuristic algorithm for the guardhouse problem based on the gradient VAP algorithm.