Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

From a viewpoint outside a circle in the plane, only part of the circle is visible, where a point on the circle is visible from the viewpoint if the line segment from the viewpoint to the point on the circle meets no other point of the circle. Call the set of points of the circle that are visible from a given viewpoint the partial view from the viewpoint of the circle. The partial views of enough viewpoints cover the circle (by compactness). What is the minimum number of viewpoints whose partial views cover the circle? Three. Jack up the dimension, and ask the same question about a sphere. The minimum number of viewpoints whose partial views cover the sphere is five. Why? Say there is a viewpoint over the North pole. Then the equator is not seen, no matter how far away is the the viewpoint. Likewise, from beneath the South pole a viewpoint cannot see the equator. So, from those two viewpoints the partial views see all of the sphere except for a (possibly very narrow) band around the equator. By the result for the circle, three more viewpoints are necessary to cover the band.

My question is, what is there in the mathematical literature that addresses the general question of determining the minimum number of viewpoints required to cover a given smooth shape in three-dimensional Euclidean space? For example, what is that minimum number for a torus? Six.

share|improve this question
1  
Why is it six for a torus? And which torus? –  Igor Rivin Jan 11 '12 at 15:11
3  
I don't know about the literature but just a comment on the numbers in your examples: for a sphere in 3D I'd say the correct number is 4 (not 5), and for a torus it should be 4 or 5 (and not 6)? –  Tapio Rajala Jan 11 '12 at 15:12
2  
Note also that the number is not always finite. –  Igor Rivin Jan 11 '12 at 15:12
    
On the same track as Tapio above, the sphere is surely viewed entirely from the vertices of a tetrahedron entirely containing the sphere? This would prove the right number to be at most 4. Your example doesn't prove minimality, rather, it bounds the minimal example from above. –  Mikael Vejdemo-Johansson Jan 11 '12 at 15:51
    
For a tangentially related MO question, see "Shortest closed curve to inspect a sphere": mathoverflow.net/questions/69099 –  Joseph O'Rourke Jan 11 '12 at 16:07
show 1 more comment

2 Answers

This is very far from a full answer but for a centrally symmetric smooth compact convex body $S$ in $\mathbb R^n$ the "visibility" number is $n+1$. In particular, for a ball in $\mathbb R^3$ it's 4. The interesting part is to bound the minimal number from below.

Suppose $k$ points $p_1,\ldots, p_k$ is enough. Let $U_i$ be the region of the boundary of $S$ visible from $p_i$. Observe that since $S$ is smooth and centrally symmetric, no $U_i$ contains any antipodal points. That means that their projections to $\mathbb{RP}^{n-1}$ are injective and we get a covering of $\mathbb{RP}^{n-1}$ by $k$ contractible sets. Therefore $k$ is bigger than or equal to the 1+(cup-length of $\mathbb{RP}^{n-1})=1+(n-1)=n$. (This is a very easy to prove and well-known fact about Lusternik-Schnirelmann category). This gives a lower bound $k\ge n$. But it can be improved to $n+1$. Suppose $n$ points are enough. If we remove one point then by above the projections of the sets $U_1,\ldots U_{n-1}$ don't cover $\mathbb{RP}^{n-1}$. Hence there is a pair of antipodal poits in $S$ not covered by any of $U_1,\ldots U_{n-1}$. That means that both of these points must be covered by $U_n$ which is impossible. Therefore $k\ge n+1$.

Note that smoothness of $S$ is key in the above argument. For example a double of a round cone in $\mathbb R^n$ along the base is visible from just two points for any $n$.

Lastly, let me echo Igor Rivin's remark that for a non-convex compact body the visibility number can be arbitrary high so I don't think anything meaningful can be said there.

edit: I see from Joseph O'Rourke's comment that this is a well-studied problem so I assume the above must be well-known.

share|improve this answer
add comment

To expand on my comment about the non-smooth equivalent problem, the problem is discussed in Brass, Moser, Pach, Research Problems in Discrete Geometry, Sec. 3.3, under the title "Levi-Hadwiger covering problem and illumination." They say this about the smooth version [p.136]:

Levy [Le55] had already observed that if $C$ has a smooth boundary (i.e., no two supporting hyperplanes pass through the same boundary point of $C$), then $H(c)=d+1$.
     Le55

Here $C$ is a convex body, and $H(C)$ is "the least integer $H$ such that $C$ can be covered by $H$ smaller homothetic copies of itself." Boltyanski proved that an illumination version of this problem (which may be the same as what the OP posed above [but see below]) has the identical answer for any $C$. So I think that Vitali Kapovitch's answer is the answer for arbitrary smooth $C$.

Another source for the non-smooth case is the Wikipedia article "Hadwiger conjecture (combinatorial geometry)." Cubes/hypercubes or parallelepipeds seem to be the worstcase; in fact, that is Hadwiger's conjecture. In $\mathbb{R}^3$, 16 lights are known to suffice, but it is seems likely that no more than 8 are needed. But please note the specific definition of illumination/visbility:

For the purposes of this problem, a body is only considered to be illuminated if for each point of the boundary of the body, there is at least one floodlight that is separated from the body by all of the tangent planes intersecting the body on this point; thus, although the faces of a cube may be lit by only two floodlights, the planes tangent to its vertices and edges cause it to need many more lights in order for it to be fully illuminated.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.