8
$\begingroup$

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.

enter image description here

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... enter image description here

|cite|improve this question
$\endgroup$
  • $\begingroup$ This is a very nice question! My "answers" below do not answer it. Might be NP-hard. $\endgroup$ – Joseph O'Rourke Jun 7 '18 at 11:18
  • $\begingroup$ Although the Art Gallery problem is NP-Hard, I don't think this one is. The visibility polygon from a point can be thought of dually as the pencil of line segments. This, in turn, maps to a "circle" in the visibility complex (cf Michel Pocchiola 1993 or 1996). So, the polygon area is the integral of the segment lengths along the complex. I think looking for the maximum will be like solving a system of linear equations. One caveat: I don't know what the space of points (i.e. segment pencil "circles") looks like in the viz complex, or if that subdivides as nicely as I think it does. $\endgroup$ – Larry B. Jun 18 '18 at 19:09
1
$\begingroup$

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

          MitchellVisib

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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

          GhoshFig

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.