Jump to content
BrainDen.com - Brain Teasers
  • 0

Illuminating a polygon


bonanova
 Share

Question

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?

  • Downvote 1
Link to comment
Share on other sites

5 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...