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 6639 articles. 1 followers. Post

5 Replies
39 Views

Similar Articles

[PageSpeed] 37


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

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 simulation
X-No-Archive Hello, I am teaching myself about java threads and concurrency, and have a textbook exercise that I am trying to implement, but I am not sure if my design is even on the right track. The problem is to model an intersection with trafficlights and 2 sensors at each trafficlight, one for arriving and entering, and one for exiting..., and cars as threads. the time the car stays in for, the length of time it takes the lights to switch colors, and the number of cars must all be definable and easy to change.. I was consiering having each car as a thread, and sensors and trafficlight...

No Intersections Snap?
Can't get the intersection snap to work on a 2d sketch. The intersections box is checked in system settings under snaps also tried to select it with the rmb menu. Is there some setting I'm missing? On Apr 22, 8:14 pm, "Chris Darwin" <nos...@nospam.com> wrote: > Can't get the intersection snap to work on a 2d sketch. > > The intersections box is checked in system settings under snaps > > also tried to select it with the rmb menu. > > Is there some setting I'm missing? When this kind of weird crap starts happening in SW 2007 I reboot...

Intersecting rectangles
Hello. I have a set of arbitrary oriented rectangles on a 2-dimensional plane. I need an algorithm to detect if there is an intersecting pair and return one such pair when it exists. I tried searching Google but I couln'd even find an algorithm to determine if two arbitrary oriented rectngles intersect (probably wrong keywords...). Ivan > Hello. > > I have a set of arbitrary oriented rectangles on a 2-dimensional plane. > I need an algorithm to detect if there is an intersecting pair and > return one such pair when it exists. So you got two problems: 1) How to detect...

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

intersection of circles
Surprisingly, the following problem isn't easily handled by a couple of scientific computing packages: If solution(s) exist, find the intersection points of two circles in the x-y plane. This requires solving a system of two qudratic equations in two variables: 1) (x - a)^2 + (y - b)^2 = r1^2 2) (x - c)^2 + (y - d)^2 = r2^2 where the points (a, b) and (c, d) are the centers of two circles of radii r1 and r2. For example, if I take a = b = 0, c = d = 0.5, and r1 = r2 = 1, the two intersection points may be found using Wolfram Alpha. However, using the solve() function...