5
$\begingroup$

We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon.

The art-gallery theorem states that $\left\lfloor\frac{n}{3}\right\rfloor$ points are sufficient (and sometimes necessary) to cover an $n$-gon and in particular this shows that polygons for which $n\le 5$ are necessarily star-shaped. However, the point which the art-gallery theorem selects is always a vertex of the polygon. I am interested in points for the interior of the polygon.

The main question I have is: Given an $n$-gon for $n\le5$, we know that the closed $n$-gon is star-shaped. Is the open $n$-gon also necessarily star-shaped? In other words, is the intersection of the kernel with the interior non-empty?

Intuitively, this should be possible by simply taking a point "sufficiently close" to vertex which oversees the polygon, but I am having difficult time finding a rigorous proof.

Also note that this is not true for $n\ge 5$. For example, the following hexagon is star-shaped from the red vertex, but the open hexagon is not star-shaped.

                                                   star-shaped hexagon

As an off-shoot of the above, I would also like to know whether this can generalize the art-gallery theorem: Is $\left\lfloor \frac{n}{3}\right\rfloor$ points in the interior of the polygon sufficient to cover it?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Also, the art-gallery theorem does not "select vertices." Perhaps a certain algorithm does, but the theorem as originally proposed applies to any point in the interior or the boundary, not just on the vertices. See, for example, the first few pages of O'Rourke's Art Gallery Theorems and Algorithms (1987, Oxford University Press). $\endgroup$ – Joel Reyes Noche Dec 2 '12 at 9:33
  • 1
    $\begingroup$ @JoelReyesNoche Well I guess "select" was a poorly chosen word on my part. I was merely trying to emphasize the fact that the proof of the art-gallery theorem constructs a guard set on the vertices of the polygon. Also, I know the theorem applies to the interior or the boundary, but I am interested in only the interior which is more limiting. $\endgroup$ – EuYu Dec 2 '12 at 9:39
  • $\begingroup$ I've deleted my first comment, the one that @EuYu refers to above, because it was based on my misunderstanding the question. For the record, I mentioned that the Wikipedia article states that "Chvátal's upper bound remains valid if the restriction to guards at corners is loosened to guards at any point not exterior to the polygon." $\endgroup$ – Joel Reyes Noche Dec 2 '12 at 9:41
4
$\begingroup$

For every polygon with at most 5 edges there is a triangulation where all diagonals meet in a single point $v$. This point is a visibility center, since every triangle can be seen from it.

enter image description here

In this triangulation every triangle has positive area. Hence we can perturb $v$ in any direction such that we still have a triangulation. If we perturb towards the polygon then the new point lies in the visibility kernel.

We can discuss this right away for the general $n$-gon setting. Also the classical approach goes via a triangulation argument. Here, every guard is responsible for an area formed by a "fan" of triangles. Again we can perturb the triangulation and add the perturb point. Then we add 2 new triangles to the perturbed triangulation and observe, that the perturbed point can see all of the "fan". This is not super-formal. But the idea should be clear.

enter image description here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the answer, the idea is indeed clear. I am guessing the fact that a valid perturbation always exists is because the area of a triangle is a continuous function of it's vertices? $\endgroup$ – EuYu Dec 2 '12 at 8:30
  • $\begingroup$ Exactly, the signed triangle area is a simple polynomial in the coordinates of the vertices. $\endgroup$ – A.Schulz Dec 2 '12 at 9:11

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.