Article citationsMore>>

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.

has been cited by the following article:

• 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 .