Author |
Topic: Beacons on a Sphere (Read 426 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Beacons on a Sphere
« on: Oct 31st, 2003, 1:18am » |
 Quote  Modify
|
Consider the unit sphere in [bbr]n. Somewhere on the surface of the sphere is a point P.
You have beacons B1 through Bk which will be placed on the surface of the sphere. Each beacon returns one value: the spherical distance between itself and the point P.
What are the conditions on k and the location placements of B1 through Bk which will allow you to uniquely determine the location of P, for all possible P [in] [bbr]n?
Note: By spherical distance, we mean the non-negative distance between the beacon B and the point P, measured along the surface of the sphere. It is the reading you would get by pressing a measuring tape along the sphere's surface, and measuring the distance between B and P. You can also think of it this distance as simply the angle between vectors B and P, measured in radians, lying between 0 and [pi]. (Recall that on a circle, the length of the arc subtended by an angle is given by the radius times the angle measured in radians. Thus, for unit radius spheres, spherical distance between two points on the surface is equal to the angle between them.)
Source: Stephen Boyd
Edit: Noted that we wanted to be able to determine P FOR ALL possible P. 5:43 PM 11/3/2003
|
| « Last Edit: Nov 3rd, 2003, 5:43pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Beacons on a Sphere
« Reply #1 on: Oct 31st, 2003, 7:24pm » |
Quote Modify
|
Perhaps I am missing something, but this seems trivial to me:
k = 3 and the three beacon points cannot be colinear (i.e. they do not all three lie on the same great circle). Note that this implies that they are also distinct and do not include antipodal pairs.
Any two non-antipodal beacons will determine, from the measured distances, two circles on the sphere. These circles must both include P, so they intersect, and since the centers are distinct and not antipodal, they intersect in at most 2 points. The circle determined by the third beacon cannot pass through both points, because if it did, the three beacons would be colinear. So the common intersection of the three circles is uniquely P.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Beacons on a Sphere
« Reply #2 on: Oct 31st, 2003, 7:54pm » |
Quote Modify
|
A counterexample: "k=1 and B1 is at P" is also a satisfactory condition.
edit: no longer applies
|
| « Last Edit: Nov 3rd, 2003, 6:30pm by Rezyk » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Beacons on a Sphere
« Reply #3 on: Oct 31st, 2003, 8:40pm » |
Quote Modify
|
Not by my understanding of the problem. The idea is to have beacons that uniquely locate P no matter where P is. K=1 only uniquely identifies 2 points.
You are not given where P is when locating the beacons. Rather you must find P from the beacons' information.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Beacons on a Sphere
« Reply #4 on: Oct 31st, 2003, 11:54pm » |
Quote Modify
|
Icarus, are you considering the general case, or just n=3?
Note, that in the plane case, 2 beacons will suffice, assuming the conditions similiar to yours.
As for the general case - here's an oversimplified reasoning: [smiley=blacksquare.gif]The locus of points on an n-sphere "spherically equidistant" from a given beacon, is an (n-1)-sphere (am I right?). If so, k = n.[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Beacons on a Sphere
« Reply #5 on: Nov 1st, 2003, 7:05am » |
Quote Modify
|
So I WAS missing something - I failed to notice the arbitrary number of dimensions. So then, the answer would be: first of all, k = n, as Barukh said. The intersection of an Sr sphere and an Ss sphere is a sphere of dimension [le] min{r, s}, with min{r,s} being possible only if one sphere is contained within the other. So, beacon 1 determines an Sn-2 sphere. If beacon 2 is not antipodal or at the same place as beacon 1, its sphere will intersect with beacon 1's to produce an Sn-3 sphere. Beacon 3's sphere will intersect with that to produce an Sn-4 sphere (assuming good placement), etc. Finally, Beacon n-1's sphere will intersect to produce an S0 sphere. But this sphere consists of 2 points. To uniquely identify which point is P, one more beacon is needed, bringing the total to n.
In order for this to work, the beacons need to be placed so that no intersection of the Sn-2 spheres of a group of them ever lies entirely within the sphere of any beacon not in the group, regardless of the radii of the spheres. My guess right now is that this is equivalent to saying that the beacons must be in "general position". I.e.: no three are all on the same great circle (an S1 sphere), no four are all on the same great S2 sphere, no five are all on the same great S3 sphere ...
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Beacons on a Sphere
« Reply #6 on: Nov 3rd, 2003, 5:50pm » |
Quote Modify
|
Edited problem statement to explicitly say that we want to uniquely determine P for any possible P in [bbr]n.
The points lying on a great circle condition is a correct description of what placements will not work (and thus the complement of this condition describes placements which will work), but it's kind of hard to see in more dimensions than 3. There's a simple and nice non-geometric proof for this problem that might be preferable.
|
| « Last Edit: Nov 4th, 2003, 11:09pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Beacons on a Sphere
« Reply #8 on: Apr 9th, 2004, 11:53pm » |
Quote Modify
|
The (poorly designed) hint was intended to suggest dot product. Here's a solution that uses only introductory linear algebra:
Let the unknown coordinates of P be expressed by a length-n vector x. Let ri be a length-n vector containing the coordinates of the ith beacon. Then the dot product of ri and x yields:
<ri,x> = || ri || || x || cos [theta]
where [theta] is the angle between x and ri. Since we are on the unit sphere, ||r|| = ||x|| = 1. Thus
<ri,x> = cos[theta]i
Now note that on a unit sphere, the spherical distance between two vectors is equal to the angle in between the vectors. (This folllows from the equation "arclength = radius [times] in-between angle".) Thus when the problem statement says we have all the spherical distances from P to the beacons, it's the same as saying we have all the angles { [theta]i } between the beacons and P.
We can encapsulate the application of the above equation over all beacons with a simple matrix equation:
Ax = y
where A is a [bbr]k x n matrix of row vectors corresponding to the beacon coordinates, x is a [bbr]n x 1 column vector corresponding to the unknown coordinates of P, and y is the [bbr]k x 1 column vector of { cos[theta]i } values. This equation is uniquely solvable for x if and only if the rank of A is n. In other words, we can determine P iff the beacon vectors span [bbr]n.
|
| « Last Edit: Apr 9th, 2004, 11:54pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print