Illuminating a polygon

[bonanova]

You are given a plane n-gon having no intersecting sides. That is, each segment of the perimeter has interior points on one side and exterior points on the other. We wish to illuminate the interior of the n-gon in its entirety by placing lamps at various points in its interior. Clearly, if the n-gon is convex, one lamp will suffice. Concave points, however, may cast shadows in some interior regions. Since life here in the Den is never simple, we ask about the general case:

To illuminate the interior of a simple n-gon, what is the smallest number of lamps that will always suffice? Does the answer change if we require the lamps to be placed at vertices?

[nana77]

No proof, but I think the answer is

n/2 lamps should work and placing them at vertices, especially those pointing inward, is a good place for them. So it would not matter if they have to be on vertices.

[bonanova]

No proof, but I think the answer is

n/2 lamps should work and placing them at vertices, especially those pointing inward, is a good place for them. So it would not matter if they have to be on vertices.

Your answer will surely work, but it is not the smallest number that will always suffice.

If you like, try drawing some 2p-gons, where p is 2 or 3 or 4, that are not convex.

Also, consider the fact that a triangle is always convex.

[Yoruichi-san]

n/3.

A lamp placed on the vertex of a triangle will light the entire triangle. If that vertex is shared by other triangles, it will light the other triangles as well. You can divide every polygon into triangles that share its vertices. If you color each vertex of a triangle a different color, i.e. every triangle will have a vertex of each color, then the maximum number of lamps you need is equal to the number of vertices of any one color, and of course, you would choose the color with fewest vertices. The maximum number of vertices colored by that color would be n/3.

[k-man]

n/2-1 rounded up, or in other words

1) for even n it's n/2-1

2) for odd n it's (n-1)/2

To see why, we need to look at the extreme cases. A simple n-gon can have as many a n convex vertices and as few as 3.

For n convex (0 concave) vertices we need only 1 lamp.

For n-1 convex (1 concave) we still can do with 1 lamp (easy to prove, so the exercise of the proof is left to the reader).

For n-2 convex (2 concave) we may require a second lamp in the worst case and these 2 lamps can be placed at the concave vertices.

For n-3 convex (3 concave) we may require 3 lamps in the worst case and they also can be placed at the concave vertices.

It's easy to see that for any given n-gon the number of lamps needed is no more than the number of concave vertices in the n-gon. We can represent this as L<=C, where L is the number of lamps needed and C is the number of concave vertices (C>=1).

Now let's look at the other extreme.

When there are only 3 convex vertices we can still do with only one lamp (the proof is also not very hard and I'm leaving it out)

When there are 4 convex vertices, we may need 2 lamps, for 5 convex vertices - 3 lamps and so on... The number of lamps that may be required also linearly increases as we add convex vertices from another extreme, so L<=n-C-2.

Adding these two equations we get the answer.

[bonanova]

n/2-1 rounded up, or in other words

1) for even n it's n/2-1

2) for odd n it's (n-1)/2

To see why, we need to look at the extreme cases. A simple n-gon can have as many a n convex vertices and as few as 3.

For n convex (0 concave) vertices we need only 1 lamp.

For n-1 convex (1 concave) we still can do with 1 lamp (easy to prove, so the exercise of the proof is left to the reader).

For n-2 convex (2 concave) we may require a second lamp in the worst case and these 2 lamps can be placed at the concave vertices.

For n-3 convex (3 concave) we may require 3 lamps in the worst case and they also can be placed at the concave vertices.

It's easy to see that for any given n-gon the number of lamps needed is no more than the number of concave vertices in the n-gon. We can represent this as L<=C, where L is the number of lamps needed and C is the number of concave vertices (C>=1).

Now let's look at the other extreme.

When there are only 3 convex vertices we can still do with only one lamp (the proof is also not very hard and I'm leaving it out)

When there are 4 convex vertices, we may need 2 lamps, for 5 convex vertices - 3 lamps and so on... The number of lamps that may be required also linearly increases as we add convex vertices from another extreme, so L<=n-C-2.

Adding these two equations we get the answer.

The idea that three is the fewest convex vertices is nice.

So far, y-san's approach gives the tightest upper bound.