Communications in Mathematical Sciences

Volume 9 (2011)

Number 2

Approximate solutions to several visibility optimization problems

Pages: 535 – 550

DOI: https://dx.doi.org/10.4310/CMS.2011.v9.n2.a9

Authors

Rostislav Goroshin (Courant Institute of Mathematical Sciences, New York University, New York)

Quyen Huynh (Naval Surface Warfare Center, Panama City, Florida)

Hao-Min Zhou (School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia)

Abstract

The visibility level set function introduced by Tsai et al. allows for gradient based and variational formulations of many classical visibility optimization problems. In this work we propose solutions to two such problems. The first asks where to position n-observers such that the area visible to these observers is maximized. The second problem is to determine the shortest route an observer should take through a map such that every point in the map is visible from at least one vantage point on the route. These problems are similar to the “art gallery” and “watchman route” problems, respectively. We propose a greedy iterative algorithm, formulated in the level set framework as the solution to the art gallery problem. We also propose a variational solution to the watchman route problem which achieves complete visibility coverage of the domain while attaining a local minimum of path length.

Keywords

visibility, optimization, level set method

2010 Mathematics Subject Classification

35-xx, 49-xx, 65-xx

Published 21 December 2010