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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .