Determining the point from which the most area in a polygon is visible

Question

I am wondering about the following problem: Given a polygon and the set of points $S$ inside it, what are the point(s) in $S$ from which the most area in $S$ is visible? Furthermore, what is the maximum visible area?

Here, I define $q$ to be visible from $p$ if the line segment between $p$ and $q$ is contained in $S$. This intends to capture the intuitive idea of what points in a room are visible when standing somewhere in the room. For example, in the figure below, the dark blue area is visible from point P, at the center of the top left quarter. The light blue area is not.

While the answer for any star-shaped domain is clear, finding the answer for arbitrary polygons seems difficult.

Question: How can we find the solution to the problem for a given polygon?

For example, the problem is not so easy for the polygon below...

Answer 1

The following paper explores heuristics for greedy coverage of a polygon by guards. The first guard selected by their various algorithms is then an approximation to what you seek.

Amit, Yoav, Joseph SB Mitchell, and Eli Packer. "Locating guards for visibility coverage of polygons." International Journal of Computational Geometry & Applications 20, no. 05 (2010): 601-630. (PDF download of preliminary version.)

---

         

---

Answer 2

This is not an answer to your question, but an answer to a related question that you might find interesting. The paper below computes "the maximum clique in the visibility graph $G$ of a simple polygon $P$ in time $O(n^2 e)$, where $n$ and $e$ are number of vertices and edges of $G$ respectively."

Ghosh, Subir Kumar, Thomas Caton Shermer, Binay Kumar Bhattacharya, and Partha Pratim Goswami. "Computing the maximum clique in the visibility graph of a simple polygon." Journal of Discrete Algorithms 5, no. 3 (2007): 524-532. (Elsevier link to HTML.)

---

         

---