Intersection of a hypersphere and a hyperplane

Hi,
I am trying to determine the solution to the following problem;
a set of weights, {a1,a2,....,an}  are needed that have the following
constraints:
sum of weights equal to one           ==>  a1+a2+...+an=1     
(Hyperplane)
Sum of weights square is equal to one ==>
a1^2+a2^2+....+an^2=1(Hypersphere)

so the solution space is simply the intersection between the
hyperplane and the hypersphere.
these are the solutions for the simplier 2D and 3D cases
2D case:
the solutions is trivial and simply (0,1) and (1,0)

3D case:
solution can be parameterized by

a1=1/3 + 2/3 * Cos(t)
a2=1/3 + 2/3 * Sin(-pi/6 + t) 
a2=1/3 + 2/3 * Sin(-pi/6 - t) 

n-dimensional case (??)
is it possible to optain a parameterized solution similar to th 3D
case ?
0
6/24/2004 3:22:58 AM
comp.graphics.algorithms 6656 articles. 1 followers. Post Follow

5 Replies
73 Views

Similar Articles

[PageSpeed] 54
"mishal" <mishalguard-main@yahoo.com> wrote in message
news:9539d010.0406231922.7cd00a5@posting.google.com...

> n-dimensional case (??)
> is it possible to optain a parameterized solution similar to th 3D
> case ?

Let U[n] = (1,...,1)/sqrt(n), a unit-length vector.  Let
A = (a[1],...,a[n]).  Choose an orthonormal basis that
includes U[n], say {U[1],...,U[n]}.  That is, U[i] has
unit-length and Dot(U[i],U[j]) = 0 for i not equal to j.
You can represent A = b[1]*U[1]+...+b[n]*U[n].
Your equations are

(1) 1/sqrt(n) = Dot(U[n],A) = b[n]
(2) b[1]^2 + ... + b[n]^2 = 1

Replace (1) in (2) to obtain
  b[1]^2 + ... + b[n-1]^2 = 1 - 1/sqrt(n)

This is the equation for a hypersphere in an
(n-1)-dimensional space and has radius
r = sqrt(1 - 1/sqrt(n)).  Any parameterization of
this object will do.  To illustrate one such
parameterization, consider n = 4.
  b[1]^2 + b[2]^2 + b[3]^2 + b[4]^2 = r^2

Let x^2 = b[1]^2 and y^2 = b[2]^2 + b[3]^2 + b[4]^2.
Set r1 = r.  Then x^2 + y^2 = r1^2.  Choose
  x = r1*cos(t1), y = r1*sin(t1)
for a parameter t1.  Now you have
  b[2]^2 + b[3]^2 + b[4]^2 = y^2 = (r1*sin(t1))^2
Choose x^2 = b[2]^2 and y^2 = b[3]^2 + b[4]^2.  Set
r2 = r1*sin(t1).  Then x^2 + y^2 = r2^2.  Choose
  x = r2*cos(t2), y = r2*sin(t2)
for a parameter t2.  Repeat again.  In the end you have

  b[1] = r*cos(t1)
  b[2] = r*sin(t1)*cos(t2)
  b[3] = r*sin(t1)*sin(t2)*cos(t3)
  b[4] = r*sin(t1)*sin(t2)*sin(t3)

The pattern is clear for dimensions larger than 4.

--
Dave Eberly
http://www.magic-software.com


0
dNOSPAMeberly (1228)
6/24/2004 4:20:32 AM
mishal <mishalguard-main@yahoo.com> wrote:

> so the solution space is simply the intersection between the
> hyperplane and the hypersphere.

In other words a hyper-circle: embedded in your hyperplane, centered
around its point of closest approach to the origin.  That point is

	[1,...,1] / N

It's distance from the origin is

	sqrt((1/N)^2+ ... + (1/N)^2)
	= sqrt(N/N^2) = sqrt(1/N)

And the radius of the hypercircle is

	sqrt(1 - (sqrt(1/N))^2)
	= sqrt(1 - 1/N)
	= sqrt((N-1)/N)
 
Construct a generalized spherical coordinate system in the hyperplane
centered around that point and the parametric description of the
hypercircle should be obvious.


-- 
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
0
broeker (2903)
6/24/2004 11:11:23 AM
Thanks Dave and Hans !
I spent 4 days looking in the internet for the formulation which to me
seems like a classical problem, with no luck !
I will go ahead and program it, this will enable me to expand the
optimization problem to include more datasets instead of being
restricted to maximum of 3 sets.
Best Regards,
Mishal

"Dave Eberly" <dNOSPAMeberly@usemydomain.com> wrote in message news:<kEsCc.11827$bs4.1741@newsread3.news.atl.earthlink.net>...
> "mishal" <mishalguard-main@yahoo.com> wrote in message
> news:9539d010.0406231922.7cd00a5@posting.google.com...
> 
> > n-dimensional case (??)
> > is it possible to optain a parameterized solution similar to th 3D
> > case ?
> 
> Let U[n] = (1,...,1)/sqrt(n), a unit-length vector.  Let
> A = (a[1],...,a[n]).  Choose an orthonormal basis that
> includes U[n], say {U[1],...,U[n]}.  That is, U[i] has
> unit-length and Dot(U[i],U[j]) = 0 for i not equal to j.
> You can represent A = b[1]*U[1]+...+b[n]*U[n].
> Your equations are
> 
> (1) 1/sqrt(n) = Dot(U[n],A) = b[n]
> (2) b[1]^2 + ... + b[n]^2 = 1
> 
> Replace (1) in (2) to obtain
>   b[1]^2 + ... + b[n-1]^2 = 1 - 1/sqrt(n)
> 
> This is the equation for a hypersphere in an
> (n-1)-dimensional space and has radius
> r = sqrt(1 - 1/sqrt(n)).  Any parameterization of
> this object will do.  To illustrate one such
> parameterization, consider n = 4.
>   b[1]^2 + b[2]^2 + b[3]^2 + b[4]^2 = r^2
> 
> Let x^2 = b[1]^2 and y^2 = b[2]^2 + b[3]^2 + b[4]^2.
> Set r1 = r.  Then x^2 + y^2 = r1^2.  Choose
>   x = r1*cos(t1), y = r1*sin(t1)
> for a parameter t1.  Now you have
>   b[2]^2 + b[3]^2 + b[4]^2 = y^2 = (r1*sin(t1))^2
> Choose x^2 = b[2]^2 and y^2 = b[3]^2 + b[4]^2.  Set
> r2 = r1*sin(t1).  Then x^2 + y^2 = r2^2.  Choose
>   x = r2*cos(t2), y = r2*sin(t2)
> for a parameter t2.  Repeat again.  In the end you have
> 
>   b[1] = r*cos(t1)
>   b[2] = r*sin(t1)*cos(t2)
>   b[3] = r*sin(t1)*sin(t2)*cos(t3)
>   b[4] = r*sin(t1)*sin(t2)*sin(t3)
> 
> The pattern is clear for dimensions larger than 4.
0
6/24/2004 7:04:24 PM
Dave,
I have substituted values in the 4D case to check and it seems that it
does conform to the quadratic constraint (second constraint) but does
not fall on the hyperplane ( first constraint).
Am I missing something ?


"Dave Eberly" <dNOSPAMeberly@usemydomain.com> wrote in message news:<kEsCc.11827$bs4.1741@newsread3.news.atl.earthlink.net>...
> "mishal" <mishalguard-main@yahoo.com> wrote in message
> news:9539d010.0406231922.7cd00a5@posting.google.com...
> 
> > n-dimensional case (??)
> > is it possible to optain a parameterized solution similar to th 3D
> > case ?
> 
> Let U[n] = (1,...,1)/sqrt(n), a unit-length vector.  Let
> A = (a[1],...,a[n]).  Choose an orthonormal basis that
> includes U[n], say {U[1],...,U[n]}.  That is, U[i] has
> unit-length and Dot(U[i],U[j]) = 0 for i not equal to j.
> You can represent A = b[1]*U[1]+...+b[n]*U[n].
> Your equations are
> 
> (1) 1/sqrt(n) = Dot(U[n],A) = b[n]
> (2) b[1]^2 + ... + b[n]^2 = 1
> 
> Replace (1) in (2) to obtain
>   b[1]^2 + ... + b[n-1]^2 = 1 - 1/sqrt(n)
> 
> This is the equation for a hypersphere in an
> (n-1)-dimensional space and has radius
> r = sqrt(1 - 1/sqrt(n)).  Any parameterization of
> this object will do.  To illustrate one such
> parameterization, consider n = 4.
>   b[1]^2 + b[2]^2 + b[3]^2 + b[4]^2 = r^2
> 
> Let x^2 = b[1]^2 and y^2 = b[2]^2 + b[3]^2 + b[4]^2.
> Set r1 = r.  Then x^2 + y^2 = r1^2.  Choose
>   x = r1*cos(t1), y = r1*sin(t1)
> for a parameter t1.  Now you have
>   b[2]^2 + b[3]^2 + b[4]^2 = y^2 = (r1*sin(t1))^2
> Choose x^2 = b[2]^2 and y^2 = b[3]^2 + b[4]^2.  Set
> r2 = r1*sin(t1).  Then x^2 + y^2 = r2^2.  Choose
>   x = r2*cos(t2), y = r2*sin(t2)
> for a parameter t2.  Repeat again.  In the end you have
> 
>   b[1] = r*cos(t1)
>   b[2] = r*sin(t1)*cos(t2)
>   b[3] = r*sin(t1)*sin(t2)*cos(t3)
>   b[4] = r*sin(t1)*sin(t2)*sin(t3)
> 
> The pattern is clear for dimensions larger than 4.
0
6/26/2004 3:45:27 AM
"mishal" <mishalguard-main@yahoo.com> wrote in message
news:9539d010.0406251945.5803d458@posting.google.com...
> I have substituted values in the 4D case to check and it seems that it
> does conform to the quadratic constraint (second constraint) but does
> not fall on the hyperplane ( first constraint).
> Am I missing something ?

The idea of my post should be clear, but a couple of
errors in the presentation.  The quadratic equation for b
should have been
  b[1]^2 + ... + b[n-1]^2 = 1 - 1/n
and r = sqrt(1-1/n).

For dimension n = 4,  U[4] = (1,1,1,1)/2 and b[4] = 1/2
and r = sqrt(3/4).  You need to parameterize the sphere
  b[1]^2 + b[2]^2 + b[3]^2 = 3/4 = r^2
Same idea as in my other post,
  b[1] = r*cos(t1)
  b[2] = r*sin(t1)*cos(t2)
  b[3] = r*sin(t1)*sin(t2)

If you want to verify the original equations with the a[i],
you still need an orthonormal basis {U[1],U[2],U[3],U[4]}.
One choice is
  U[1] = (1,1,-1,-1)/2
  U[2] = (1,-1,1,-1)/2
  U[3] = (1,-1,-1,1)/2
Using A = b[1]*U[1]+b[2]*U[2]+b[3]*U[3]+b[4]*U[4]
  a[1] = (b[1]+b[2]+b[3]+b[4])/2
  a[2] = (b[1]-b[2]-b[3]+b[4])/2
  a[3] = (-b[1]+b[2]-b[3]+b[4])/2
  a[4] = (-b[1]-b[2]+b[3]+b[4])/2
The sum is
  a[1]+a[2]+a[3]+a[4] = 2*b[4] = 2*(1/2) = 1
This is true no matter how you parameterize the b[i] values.

--
Dave Eberly
http://www.magic-software.com


0
dNOSPAMeberly (1228)
6/26/2004 2:47:53 PM
Reply:
Similar Artilces:

Polygons that define the intersection of 2 surfaces
Hi all, First up, apologies in advance if I'm not using the correct terminology... I have 2 'surfaces' which are made up of a series of points in 3d space (ie. an x,y & z). On a surface, for each x,y combination there is only a single z value. The 2 surfaces may not cover the same xy extents, and they may have different spacing between each point. I would like to calculate the polygons that define the intersection of the 2 surfaces. There may be 0,1 or many intersections. I'd appreciated any pointers to algorithms, code, concepts, etc that might be useful. If there are...

intersect
is there any way to intersect / deintersect editable meshes ? (3dsmax 5) .. Tried loking in the docs but couldn't find anything.... any help appreciated. -- Eps burchill wrote: > is there any way to intersect / deintersect editable meshes ? (3dsmax 5) > . Tried loking in the docs but couldn't find anything.... > > any help appreciated. > > -- > Eps nobody knows huh ? what i have is a 2d spline that i have extruded long a 2d plane and I need to make a whole in the middle of it, anyone know how ?. -- Eps Draw a circle and attach ...

Find the equivalent intersection point of multi lines in 3D space
HI everyone, I'm not a native english speaker, so I wonder you could understand my question very well. This question originates from my physics experiments. When I catch several lights from my equipment, the light source is far away, so I should caculate the position of the equivalent "light source". This comes the post title. Normally, all these light lines were skew each other. For two lines, this is very simple to get the answer, because we can easily define the equivalent point as the mid-point of the shortest distance of the two lines. Several algorthms can be found by Goo...

Intersect
Hello, I want to kbnow if there is a means to do a query which can be like this select a,b from table 1 where conditions intersect (a) (intersection only on column a) select a,b from table 1 where other conditions intersect(a) select a,b from table 1 where another conditions etc. without a join (because i can have a lot of different conditions) Thank you for your response Ludovic wrote: > Hello, > > I want to kbnow if there is a means to do a query which can be like > this > > select a,b from table 1 where conditions > intersect (a) (inters...

intersection of bags
hi im trying to make an intersection function that takes as arguments two lists representing bags andshould return the list representing their bag-intersection. i can write a function for sets but how do i change it do work with bags (define intersection (lambda ( S1 S2 ) (cond ( (null? S1) '() ) ( (member? (car S1) S2 ) (cons (car S1) (intersection (cdr S1) S2))) (else (intersection (cdr S1) S2)))) "isaac2004" <isaac_2004@yahoo.com> writes: > hi im trying to make an intersection function that takes as arguments > two list...

Union / Intersect shapefiles
Hi Everyone This is another interesting thing that has been bugging me: Every GIS software allows one to do simple operations like Union and Intersection upon shapefiles. How does one do it in IDL? I know there are no in-built functions for it in IDL and Mr Fanning suggests I have to use some mathematics for it. But I am not sure what to use and how. Hope I get some prompt ones. Gaurav ...

cell & ismember or intersect
r=cell(10); r{1,1}=1:5; r{1,5}=6:10; In the example abvoe, I would like to know the location of 6, which is the 5th array of cell. I used intersect or ismember to find the location, but it didn't work. It says that it should be "string" in order to use "intersect" or "ismember" in cell array. I am trying to avoid loop and "string" to perform such functions in huge simulations. In the same example above, I also would like to find the first empty cell. Would you help me to do it? I used a loop "for", but in my huge simulations, I would like...

Intersection
Richard A. DeVenezia <rdevenezia@WILDBLUE.NET> wrote: >data way1; > merge a(in=ina) b(in=inb); > by i; > if ina and not inb > or inb and not ina > ; >run; The law of the excluded middle applies -- to get into data way1 a record MUST have come from either a or b To get the intersection, you code data way1; merge a(in=ina) b(in=inb); by i; if ina and inb: run; Therefore, to get the non-intersection, you can simply code data way1; merge a(in=ina) b(in=inb); by i; if not (ina and inb): run; I've heard the term "albedo" used to refer to...

Intersection
Hej I have a small problem with finding the intersection of a parametric curve with itself. The curve is defined with x(t) and y(t), meaning I have two, about 10000 elements long, vectors with spatial coordinates and I would like to know when the curve intersects with itself. I believe some kind of approximation will be needed and I am wondering if anyone has been dealing with similar problem before I start writing my own algorithm. I could create an interpolation function with 10000 basis functions but I would like to avoid this due to the stability problems of solving intepolation matrix....

Tree Automata Intersection Algorithm
I am looking for an algorithm that performs intersection operation on two tree automatas. I unable to find any in textbooks or online. Please let me know of algorithms that you may be aware of. I am not concerned with efficiency right now and would like to see a complete algorithm from ground up. <google@technologist.com> wrote in message news:1105110913.936749.229460@z14g2000cwz.googlegroups.com... > > I am looking for an algorithm that performs intersection operation on > two tree automatas. I unable to find any in textbooks or online. Please > let me know of algorithms...

ray-triangle intersection and ray-quadrics intersection
Hi, Is anyone has good links or c++ source code for ray-triangle intersection and ray-quadrics intersection? Thank you! RS RS wrote: > Is anyone has good links or c++ source code for ray-triangle intersection > and ray-quadrics intersection? Thank you! For ray-triangle intersections: "Fast Minimum Storage RayTriangle Intersection" http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf "Realtime Ray Tracing and Interactive Global Illumination" http://www.mpi-sb.mpg.de/~wald/Pu...

Line intersection
I have an image of a grid taken by a wide angle cammera,with a distortion.I want to find the intersections in this grid and replace them with dots. How could I do that? Thank you in advance nikos fot wrote: > > > I have an image of a grid taken by a wide angle cammera,with a > distortion.I want to find the intersections in this grid and > replace > them with dots. > How could I do that? > > Thank you in advance The equations for two crossing lines can be written as ax+by=e cx+dy=f; Matlab gives crossing points for such lines as X=[a b;c d]\[e;f] X containing c...

Re: Intersection of 2 Tables [was No Subject] #2
By some amazing coincidence, there is an excellent SUGI paper on this very topic: Paper 242-31: Howard Schreier SQL Set Operators: So Handy Venn You Need Them http://www2.sas.com/proceedings/sugi31/242-31.pdf Mike Rhoads Westat RhoadsM1@Westat.com -----Original Message----- From: owner-sas-l@listserv.uga.edu [mailto:owner-sas-l@listserv.uga.edu] On Behalf Of Howard Schreier <hs AT dc-sug DOT org> Sent: Wednesday, April 12, 2006 1:00 PM To: SAS-L@LISTSERV.UGA.EDU Subject: Intersection of 2 Tables [was No Subject] On Wed, 12 Apr 2006 16:40:57 +0000, toby dunn <tobydunn@HOTMAIL....

ray-triangle intersection and ray-quadrics intersection
Hi, Is anyone has good links or c++ source code for ray-triangle intersection and ray-quadrics intersection? Thank you! RS RS wrote: > Hi, > > Is anyone has good links or c++ source code for ray-triangle intersection > and ray-quadrics intersection? Thank you! > There's loads of them here: http://www.google.com/search?q=ray-triangle+intersection -- <\___/> For email, remove my socks. / O O \ \_____/ FTB. The Cheat is not dead! ...

intersections of 4th degree polynomials
Hi all!!! I'm trying to find the intersection of two polynomials of the form: p4*x^4 + p3*x^3 + p2*x^2 + p1*x = y and m4*x^4 + m3*x^3 + m2*x^2 + m1*x = y Any one has a clue about doing this in matlab?!? Please help me and forgive me if this is a dumb question XD Regards, Miki "MIKICAT Mikawer" <rubiozelada@gmail.com> wrote in message <i138ui$o41$1@fred.mathworks.com>... > Hi all!!! I'm trying to find the intersection of two polynomials of the form: > p4*x^4 + p3*x^3 + p2*x^2 + p1*x = y > and > m4*x^4 + m3*x^3 + m2*x^2 + m1*x = y > >...

Case study of working at the intersection of LaTeX, Word, and QuarkExpress
For a brief paper on this topic, see www.walden-family.com/public/book-in-ltx.pdf I don't necessarily recommend my approach (and there are surely better approaches), but some aspect of my experience may be interesting to someone struggling with a situation like I had. ...

Circle Intersection
Hi, Until recently, A. Vakulenko http://www.mathworks.com/matlabcentral/fileexchange/authors/14376 had a code posted in the file Exchange called "Circle Intersection". This code dated to 2004. It was an incredibly useful code for my project, as it could calculate analytically the total area and different overlap areas of an array of circles of different sizes in a plane. I have found no open source substitute for this code, and would loathe to have to generate something equivalent myself! I recently checked on this code again, and it is no longer available in the Fil...

Intersection, help!!!
Hello guys I need again your help...I have two function for example cos(x) and sin(x), I need to find the intersection point there is some function? Thanks stefano wrote: > > > Hello guys I need again your help...I have two function for example > cos(x) and sin(x), I need to find the intersection point there is > some function? > Thanks Uh, have you tried: >help intersect ? Alternatively if both vectors are the same length you can do: threshold=0.01; % for example indIntersect=find(abs(diff(sin(x)-cos(x)))<threshold); stefano wrote: > > > Hello guys I ne...

FAQ 4.43 How do I compute the difference of two arrays? How do I compute the intersection of two arrays? #3 448367
This is an excerpt from the latest version perlfaq4.pod, which comes with the standard Perl distribution. These postings aim to reduce the number of repeated questions as well as allow the community to review and update the answers. The latest version of the complete perlfaq is at http://faq.perl.org . -------------------------------------------------------------------- 4.43: How do I compute the difference of two arrays? How do I compute the intersection of two arrays? Use a hash. Here's code to do both and more. It assumes that each element is unique in a given ar...

intersection
I'm a bit confused about how "intersection" is supposed to work in Common Lisp. The Hyperspec says the following about intersection: "The intersection operation is described as follows. For all possible ordered pairs consisting of one element from list-1 and one element from list-2, :test or :test-not are used to determine whether they satisfy the test [of equality]....For every pair that satifies the test, exactly one of the two elements of the pair will be put in the result." That tells me that if you have 3 A's in one list and 2 A's in the other, you'l...

Intersection
Hi all, Does OpenGL provide a way to detect that two objects are intersecting ? ( for instance, to avoid an object passing through a wall ) If it doesn't, would you be so kind to tell me how I can implement such a thing without having to compare all coordinates of all objects ? TIA Hello No, OpenGL is only a 3D rendering API. For collision detection, try googling for "ray triangle collision/intersection" (yes, you need to detect collision with every triangle that may be an obstacle). There are lot of improvement to avoid detecting every triangle of the sce...

coordinates of intersection of waveform
i have two arrays plotted on the same graph. I am looking for the coordinates where these two graphs intersect. The information about the exact graph is given in the attached VI. &nbsp; thanks a lot for your help. I have a feeling that this is quite trivial but would really appreciate any help. find intersection.vi: http://forums.ni.com/attachments/ni/170/188672/1/find intersection.vi ...

Union and Intersection
How can I find the union/intersection of two patches plotted in a figure? I have created two patches using the PATCH(X,Y,C) function. Any suggestions would be welcome. (Is there a simpler way than using the polybool function in the mapping toolbox? I don't want to have to give my patches global positions and have to use map projections on them) Ian wrote: > How can I find the union/intersection of two patches plotted in a > figure? > > I have created two patches using the PATCH(X,Y,C) function. > > Any suggestions would be welcome. > > (Is there a simpler way t...

How to find the intersection point of two intersecting OBBs
I need help understanding how to find the intersection point of two intersecting oriented bounding boxes. I am building a rigid body simulator that uses oriented bounding boxes as the collision boundaries. I have got collision detection working (via separating axis approach) and am beginning to implement the collision response. Part of the collision response is to determine the magnitude of the impulse to apply to the rigid bodies. To accomplish this, I need the point of intersection of the two OBBs. I have been using David Eberly's detailed documentation (http://www.geometrictools.co...

Intersection #2
Would you like to tell me please if there is any funtion which can help me to calculate the intersection point between 2 lines? Thank you in advance y1 = b1*x + a1 % equation for line 1 y2 = b2*x + a2 % equation for line 2 b1*x + a1 = b2*x + a2 % condition for intersection x = (a2 - a1) / (b1 - b2) % x-coordinate of intersection point Did you mean that, or something else? Dimitris wrote: > Would you like to tell me please if there is any funtion which can > help me to calculate the intersection point between 2 lines? > > Thank you in advance Thanks very much Vladimir!I...