Intersection of a hypersphere and a hyperplane

  • Permalink
  • submit to reddit
  • Email
  • Follow


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
Reply mishalguard-main (3) 6/24/2004 3:22:58 AM

See related articles to this posting


"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
Reply 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
Reply 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
Reply mishalguard-main (3) 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
Reply mishalguard-main (3) 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
Reply dNOSPAMeberly (1228) 6/26/2004 2:47:53 PM
comp.graphics.algorithms 6640 articles. 1 followers. Post

5 Replies
56 Views

Similar Articles

[PageSpeed] 10


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

intersecting a hypercube and a hyperplane
Hi all, I have a problem you will laugh about (maybe). Here: You have a hypercube and a hyperplane. They intersect. In n-D the intersection region is a (n-1)-D object. I am interested in determining the vertices of the intersection object. Of course, I can check all the edges and determine all intersection vertices, but that takes n 2^(n-1) checks. Do you know of any algorithm to compute that? The hyperplane is Sum(Xi)=C, for some C, where Xi is the i-th coordinate. Idea: For each vertex of the hypercube you add its coordinates, and form a partition into three sets (ver...

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...

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 ...

hyperspherical kmeans or hyperspherical fuzzy cmeans
are there any codes about that or m files &#305; look on the net but found nothing "ali " <rebelfirst@gmail.com> wrote in message <h472l6$8qa$1@fred.mathworks.com>... > are there any codes about that or m files &#305; look on the net but found nothing Google returned me this results: hyperspherical kmeans files: http://s.pudn.com/upload_log_en.asp?e=533377 http://s.pudn.com/upload_log_en.asp?e=1207757 Tutorial on kmeans clustering matlab: http://people.revoledu.com/kardi/tutorial/kMean/matlab_kMeans.htm On pudn you have to upload something before you ...

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...

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! ...

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
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....

Robust FCM,Hyperspherical Kmeans, Hyperspherical FCMeans
hi &#305; look forward to these codes or improved this one on pudn only c codes &#305; m looking for matlab help me pls... ...

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...

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
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...

What is the distance of two intersecting circles based on the area of intersection?
Hi all, I want to draw some proper VENN diagrams in which case I have the radii and areas of two circles, and I know the area of overlap. I had a look at http://mathworld.wolfram.com/Circle-CircleIntersection.html - it solves the area of two overlapping circles dependend on the distance of the two circles from each other. I can't figure out how to solve the equation for d. Anyone here knows what the solution would be? Thanks Markus ...

(A UNION B) MINUS (A INTERSECT B) = not(A INTERSECT B)
Hello, I'm trying to determine the negation of A intersect B quicker than: (A UNION B) MINUS (A INTERSECT B) Is there a standard SQL operator that will do this? Thanks cdecarlo@gmail.com wrote: > Hello, > > I'm trying to determine the negation of A intersect B quicker than: > > (A UNION B) MINUS (A INTERSECT B) > > Is there a standard SQL operator that will do this? Subselect using NOT IN? Such as SELECT * FROM B WHERE B.id NOT IN ( SELECT id FROM A ) Not tested. It seems to be an equivalent approach, but I am not entirely su...

Matlab Hyperspherical K-Means and Hyperspherical C Means Codes
I m looking forward to these algorthms on net but there arent matlab files Kmeans and fuuzy c means's another applications or developments Has anybody know about that "ali " <rebelfirst@gmail.com> wrote in message <h4bp3p$iuu$1@fred.mathworks.com>... > I m looking forward to these algorthms on net but there arent matlab files > Kmeans and fuuzy c means's another applications or developments > Has anybody know about that FUZZY K MEANS: Search here on google: http://lmgtfy.com/?q=fuzzy+k+means+matlab+source http://www.google.com/codesearch?q=fuzz...

3 Problems with intersections function
Dear all, I am having problems with the intersections function published by Douglas Schwarz. It may be viewed here: http://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections I have 2 problems. Problem 1: The function works correctly between any two curves. Furthermore, it works correctly for x-amounts of curves if coded in a loop. My problem is that I'd like to perform the operation for any amounts of curves without a loop but so far have not been able to. The syntax is [xo,yo] = intersections(x1,y1,x2,y2) Where xo and yo represent the coordinates o...

3-D Plane Intersection: using intersection as x-axis for 2-D plots on each plane
3-D Plane Intersection: using intersection as x-axis for 2-D plots on each plane How Can I do this in simple way? I tried meshgrid but I can not do this. On Jan 7, 4:06=A0am, "Sebastian " <sebastianpszczo...@gmail.com> wrote: > 3-D Plane Intersection: using intersection as > x-axis for 2-D plots on each plane > > How Can I do this in simple way? > I tried meshgrid but I can not do this. ----------------------------------------------- The intersection of a plane and a solid 3D object (array) is a 2D planar array. How can a 2D array be used as an x-axis? ...

Surface Intersect
I have a circle a certain distance from a flat surface. I would like to extrude the circle to the surface, so that the cylinder created is capped off, but where it intersects the flat surface there is a hole. This is so I can fillet the capped surface and the intersection point with the flat surface. Then I want to thicken to have a uniform solid body. What is the best way to do this in Solidworks without a temendous amount of steps? Thank you in advance, Jack Using the "flat Surface" mentioned as your sketch plane create a new surface with no hole and use that new surface to ex...

itertools.intersect?
Hi, During a fun coding session yesterday, I came across a problem that I thought was already solved by itertools, but on investigation it seems it isn't. The problem is simple: given one or more ordered sequences, return only the objects that appear in each sequence, without reading the whole set into memory. This is basically an SQL many-many join. I thought it could be accomplished through recursively embedded generators, but that approach failed in the end. After posting the question to Stack Overflow[0], Martin Geisler proposed a wonderfully succinct and reusable solution (see belo...

Intersecting Triangles
I would like to be able to calculate the area that two 2D triangles intersect. Are there any good ways to do this in Matlab? The Triangles are defined by their vertices and I can plot them with the Patch command, but I would like to know the area of their intersection. Thanks, Kaz Kaz Maro wrote: > I would like to be able to calculate the area that two 2D triangles > intersect. Are there any good ways to do this in Matlab? The > Triangles are defined by their vertices and I can plot them with the > Patch command, but I would like to know the area of their > intersection. > ...

Intersection of DIVS
Hi There :) Is it possible to get the 4 corners where 2 dives intersect? I'm making a table-ish system and som drag and drop elements need to snap to the area intersecting between 2 divs. I don't know if this is possible? sicapitan said the following on 8/21/2006 5:18 AM: > Hi There :) > > Is it possible to get the 4 corners where 2 dives intersect? I'm > making a table-ish system and som drag and drop elements need to snap > to the area intersecting between 2 divs. > > I don't know if this is possible? Yes, quite possible. You need to know the top...

Intersecting faces
Hi all, I am using about 24 faces to approximate a cylinder and in my app there are many such cylinders and some of them overlap. The problem is that the overlapping cylinders have jagged edges where thy intersect, why is it so. Take a look at this picture for understanding what I am saying: http://www.geocities.com/romi_ssk/untitled1.JPG Any suggestions will be highly appreciated. Thanks Romi ...

intersect point
Hello, I have two vectors and I'm looking for the intersect points. Plotting the vectors they cross each other several times. But it wouldn't work with find(v1 = = v2) because the intersect point is between to points in the vectors. How can I find the real intersect points. Thanks a lot. Andrea "Andrea Schmidt" <external.Andrea.Schmidt@de.bosch.com> wrote in message <fak1t7$qbd$1@news4.fe.internet.bosch.com>... > Hello, > I have two vectors and I'm looking for the intersect points. Plotting the > vectors they cross each other several times. But i...

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...