7
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ @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 $\endgroup$ Commented Apr 30, 2013 at 19:41
  • 2
    $\begingroup$ 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 $\endgroup$ Commented Apr 30, 2013 at 21:22

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Great picture! $\endgroup$ Commented May 1, 2013 at 13:46
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ Commented Apr 30, 2013 at 14:40
  • $\begingroup$ Well, Joseph O'Rourke wrote a book on art gallery theorems. :-) $\endgroup$
    – Boris Bukh
    Commented Apr 30, 2013 at 14:51
  • $\begingroup$ 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. $\endgroup$ Commented Apr 30, 2013 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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