8
$\begingroup$

Suppose we have $4$ points that can be positioned anywhere in $\mathbb{R}^2$. Now imagine each point has $90$ degree projectors coming out of them and you can rotate these projectors any way you would like. How can one prove that no matter where the four points are you can rotate the projectors so that the whole plane will be illuminated entirely?

I would like to elaborate on illuminate. You see, if you can imagine to lines shooting out of the points where they form $90$ degree angles then the space contained inbetween the lines can be thought of as being illuminated. And so obviously if the points are positioned such that they look to be corners of a square, we can just rotate the projectors so that they look to be the sides of a square. And so then extending the projectors off to infinity we can illuminate the whole plane. This is just one case of course. I was not sure how to prove it no matter where the points are. My thought was wherever the points are try to draw an $xy$ axis such that each point is in a quadrant. Then one can just proceed to make the projectors so that they form a square like figure again. Its an interesting problem.

Heres a bonus question. Suppose there are $n$ projectors located at $n$ points where each projector illuminates $\displaystyle\frac{360}{n}$ degrees. Then one can rotate them until the whole plane is illuminated.

$\endgroup$
1
$\begingroup$

I agree with you: this is an interesting problem. Here is a solution for $n = 4$.

As you observed, it is enough to show that there exists a point $p$ in $\mathbb{R}^2$ together with a cross (with $n$ equally spaced "spokes") centered at $p$ so that each of the $n$ (closed) sectors contains one of the four points where the $n$ projectors are placed.

I claim that such a point and cross always exist when $n = 4$. Consider the convex hull of the four points and assume it is nondegenerate, i.e., the convex hull is a quadrilateral with nonempty interior. One of the angles of this quadrilateral must have angle measure at least $90^\circ$. Let $p$ be that vertex and arrange the cross so that two of the spokes are contained in the hull and the quadrant they bound contains the vertex opposite to $p$. Then this cross satisfies the requirement in the previous paragraph.

The degenerate cases (i.e., when the convex hull is a triangle and the fourth point is inside or when the four points are collinear) can be handled similarly. When the convex hull is a triangle, pick $p$ to be the point in the interior. By assumption the other three points cannot be contained in the same half-space, so we can always find a suitable cross. The case of four collinear points is easy and can be resolved without using this method. (Or one can think of it as a convex quadrilateral.)

Additional note: Solutions that arise from moving the projector backwards are those for which there is a point that is simultaneously illuminated by all $n$ projectors. Of course, it may be the case that this approach fails for some $n \neq 4$.

Let me know if any of the steps in the procedure is unclear. It's hard to explain it in words.

$\endgroup$
  • $\begingroup$ I am not sure what you mean by words such as spokes, hull, convex hull, and nondegenerate. Sorry maybe clarify what you mean by these and I will try to piece your argument together. $\endgroup$ – Nick Freeman Sep 17 '14 at 2:42
  • $\begingroup$ Ok, "spokes" are what you call the $xy$-axis in your question - basically I am referring to the four rays emanating from the point. "Hull" or "convex hull" is formally defined to be the smallest convex set containing the four points. Imagine four pegs sticking out at the four points, and wrapping a rubber band around them; the region inside the rubber band is the convex hull. Depending on how the pegs are positioned, you may get a quadrilateral, a triangle, a line segment, or even a point. The first case is what I mean by "nondegenerate". $\endgroup$ – JHF Sep 17 '14 at 2:49
  • $\begingroup$ I think your idea works. Good work. Now we just need to figure out the case for $n$ points :) $\endgroup$ – Nick Freeman Sep 17 '14 at 3:08
  • $\begingroup$ I seem to have found a limitation to this method. Consider the case $n = 6$ where the six points are arranged in two groups of three (yes they overlap). Then no such $p$ exists. Proof: if $p$ is not one of the clusters, then at best the three projectors belong to the same two sectors at $p$, which is bad. Nonetheless, there is a still a way to illuminate the entire plane, but no point is simultaneously illuminated. $\endgroup$ – JHF Sep 17 '14 at 3:59
1
$\begingroup$

Here is a way which works when $n$ is even. Choose a line where half of the points are on each side, and think of this line as horizontal. We first illuminate the upper half plane with the projectors in the lower half. Let $\theta=360/n$. Of the lower projectors, let $p_1$ be the one which is northmost when the plane is rotated clockwise by $\theta$. Aim $p_1$ so that the clockwise edge of its light is horizontal and to the right of $p_1$. In general, $p_k$ will be the projector not among $p_1,\dots,p_{k-1}$ which is northmost when the plane is rotated clockwise by $k\theta$, and the clockwise edge of $p_k$'s light should make an angle of $(k-1)\theta$ with the horizontal ray to the right of $p_k$. Because of the ``northmost when rotated by\dots" condition, the light cones of $p_k$ and $p_{k+1}$ will overlap in such a way that the entire upper half is covered.

Repeat this procedure with the projectors in the upper half plane, and the entire plane will be illuminated.

I believe a similar procedure can be applied when $n$ is odd, provided you can find a line which intersects one projector, divides the remaining projectors in half, and where this projector can be rotated so the line bisects its light and it illuminates no other projectors.

$\endgroup$
0
$\begingroup$

Here is an other way to solve the 4 points porblem. I write it as it may help for the general problem.

There is always a line $L$ that separates the points in 2 sets of $\frac{n}{2}$ points. To find one, take any line not aligned with the directions of any 2 points, and consider its parallels.

In each set, you can sort the points "from left to right" regarding $L$.

For each point of a set, direct the spot such as:

  • one border is parallel to $L$
  • one border intersects $L$
  • the "left" point illuminates to the "right" and the "right" point to the "left"

This way, the 2 points of an half space will illuminate completely the other half space

$\endgroup$

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.