wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Beacons on a Sphere
        
(Message started by: william wu on Oct 31^st, 2003, 1:18am)

Title: Beacons on a Sphere
Post by william wu on Oct 31^st, 2003, 1:18am

Consider the unit sphere in [bbr]ⁿ. Somewhere on the surface of the sphere is a point P.

You have beacons B₁ through B_k 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 B₁ through B_k which will allow you to uniquely determine the location of P, for all possible P [in] [bbr]ⁿ?

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

Title: Re: Beacons on a Sphere
Post by Icarus on Oct 31^st, 2003, 7:24pm

Perhaps I am missing something, but this seems trivial to me:
[hide] 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.[/hide]

Title: Re: Beacons on a Sphere
Post by Rezyk on Oct 31^st, 2003, 7:54pm

~~A counterexample: "k=1 and B₁ is at P" is also a satisfactory condition.~~

edit: no longer applies

Title: Re: Beacons on a Sphere
Post by Icarus on Oct 31^st, 2003, 8:40pm

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.

Title: Re: Beacons on a Sphere
Post by Barukh on Oct 31^st, 2003, 11:54pm

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][hide]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.[/hide][smiley=blacksquare.gif]

Title: Re: Beacons on a Sphere
Post by Icarus on Nov 1^st, 2003, 7:05am

So I WAS missing something - I failed to notice the arbitrary number of dimensions. So then, the answer would be: [hide] first of all, k = n, as Barukh said. The intersection of an S^r sphere and an S^s 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 S^n-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 S^n-3 sphere. Beacon 3's sphere will intersect with that to produce an S^n-4 sphere (assuming good placement), etc. Finally, Beacon n-1's sphere will intersect to produce an S⁰ 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 S^n-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 S¹ sphere), no four are all on the same great S² sphere, no five are all on the same great S³ sphere ...[/hide]

Title: Re: Beacons on a Sphere
Post by william wu on Nov 3^rd, 2003, 5:50pm

Edited problem statement to explicitly say that we want to uniquely determine P for any possible P in [bbr]ⁿ.

The [hide]points lying on a great circle[/hide] 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.

Title: Re: Beacons on a Sphere
Post by william wu on Nov 5^th, 2003, 6:36pm

Hint: ::[hide] . [/hide]::

Title: Re: Beacons on a Sphere
Post by william wu on Apr 9^th, 2004, 11:53pm

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 r_i be a length-n vector containing the coordinates of the i^th beacon. Then the dot product of r_i and x yields:

<r_i,x> = || r_i || || x || cos [theta]

where [theta] is the angle between x and r_i. Since we are on the unit sphere, ||r|| = ||x|| = 1. Thus

<r_i,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]ⁿ.