Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
@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
2  
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
add comment

2 Answers 2

up vote 6 down vote accepted

Here is an argument, a revision (and replacement) of one I sketched earlier.

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 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:
        VisibSeg

share|improve this answer
    
Great picture! –  Joel David Hamkins May 1 '13 at 13:46
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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