# Intersection of 2 visibility polygons

Let $P$ be a simple, closed and bounded polygon and $p_1,p_2 \in \mathrm{int}(P)$ be two points in its interior. Is it true that the intersection of the visibility polygons of $p_1$ and $p_2$ is connected?

The visibility polygon of a point $p\in P$ is the set of all $x \in P$ such that the line segment connecting $p$ and $x$ is contained in $P$.

It might be elementary, but we fail either finding a proof or a counterexample. Furthermore, in the literature I could only find details about the computational aspects of the visibility polygon, but not a single word about its properties. Any reference, example, sketch of proof etc. is welcomed!

• @Dror: You might also look at the work of Marilyn Breen, and the work she cites in her papers: informatik.uni-trier.de/~ley/pers/hd/b/Breen:Marilyn.html – Joseph O'Rourke Apr 30 '13 at 19:41
• The argument needs to use dimension 2 as there are analogous cases in 3 dimensions where the intersection is not connected. Gerhard "Ask Me About Blind Corners" Paseman, 2013.04.30 – Gerhard Paseman Apr 30 '13 at 21:22

## 2 Answers

Yes. Here is an argument.

Let $p_1$ and $p_2$ both see $a$ and $b$. I claim that every point along the shortest path $\sigma$ connecting $a$ to $b$ inside $P$ is visible to both $p_1$ and $p_2$. With this claim established, we know the intersection of the visibility polygons is connected.

Start turning/sweeping the rays $p_1 a$ and $p_2 a$ counterclockwise along $\sigma$ toward $b$, simultaneously tracking the same point $x$ along $\sigma$. If both rays remain unobstructed throughout the sweep, we are finished. So suppose otherwise. Then one or the other ray, say $p_2 a$, must encounter an obstruction, a reflex vertex $v$ hitting $p_2 a$, blocking the visibility to point $x \in \sigma$. Then we have some exterior points of the polygon enclosed within the closed path $p_2 x \cup \sigma(x,b) \cup b p_2$ of points interior to $P$, contradicting the simplicity of the polygon, i.e., the polygon has a hole: The answer is yes. I do not see a clean proof. Here is a proof by case-checking. Consider two points $q$ and $q'$ that are visible from both $p_1$ and $p_2$. There are several cases:

1) Suppose four points $p_1$, $p_2$, $q$, $q'$ are in convex position, and points $p_1$, $p_2$ are opposite vertices of the convex hull. Then convex hull is completely inside the polygon, and in particular in the intersection of two visibility polygons. Thus, $q$ and $q'$ are in the same connected component.

2) Four points $p_1$, $p_2$, $q$, $q'$ are in convex position, and points $p_1$, $p_2$ are adjacent vertices of the convex hull. Without loss, assume that the order is $p_1$, $p_2$, $q$, $q'$. Let $r$ be the intersection point of line segments $p_1q$ and $p_2q'$. Then the line segments $qr$ and $q'r$ are contained in the intersection of visibility regions.

3) Point $q$ is in the convex hull of $p_1$, $p_2$ and $q'$. Then the nonconvex $4$-gon $p_1qp_2q'$ is in the intersection of visibility polygons, and line segment $qq'$ is completely contained in it.

4) Point $p_1$ is in the convex hull of $p_2$, $q$ and $q'$. In that case the line segments $qp_1$ and $q'p_1$ are in both visibility polygons. Again, $q$ and $q'$ are connected.

• Are you familiar with some references where these kind of things are shown/proven? There might be more things of that sort that will be useful for me. Thank any way! – Dror Atariah Apr 30 '13 at 14:40
• Well, Joseph O'Rourke wrote a book on art gallery theorems. :-) – Boris Bukh Apr 30 '13 at 14:51
• As far as I understood this book is mainly about the algorithms related to the art gallery, isn't it? Anyway, I'll have a closer look. – Dror Atariah Apr 30 '13 at 19:01