f



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 6670 articles. 0 followers. Post Follow

5 Replies
222 Views

Similar Articles

[PageSpeed] 59

"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:

intersection algorithms
Hello! Can anyone help me with url(s) to algorithms or with algorithms for intersections: (2D only) line(segment) x circle line(segment) x ellipse circle x circle circle x ellipse ellipse x ellipse regards, New Age "New Age" <new_age@nomail.me> wrote in message news:H4udnT5ZGpf28KLcRVn-tg@giganews.com... > Can anyone help me with url(s) to algorithms or with algorithms for > intersections: > (2D only) > > line(segment) x circle > line(segment) x ellipse The circle/ellipse is represented by a quadratic equation F(x,y) = 0. A line is parameterized by (x,y) = P+t*D, where P is a point on the line, D is a unit-length direction vector, and t is any real number. A line segment has the additional restriction that t is in some interval [t0,t1]. Replace the parameterization in the quadratic equation to obtain Q(t) = F(P+t*D) = 0, a quadratic equation in the single variable t. Compute the roots of Q(t) = 0. If the roots are not real-valued, the line does not intersect the circle/ellipse (so neither does a line segment). If there is a single repeated real-valued root r, then the line is tangent to the circle/ellipse at the point P+r*D. If r is in the interval [t0,t1], then the segment is tangent to the circle/ellipse. Finally, if there are two distinct real-valued roots r0 and r1, the line intersects the circle/ellipse in two points P+r0*D and P+r1*D. If either root is in [t0,t1], then the segment intersects the circle/ellipse. > c...

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

Graphic algorithms are bogus
I think all the algorithms are crap, not useful at all.Old programs on the IBM PC were much faster on a 4.77 Mhz machine than the crap of today. I think we should use ASCII graphics again. And Carl Dau said... > I think all the algorithms are crap, not useful at all.Old programs on the > IBM PC were much faster on a 4.77 Mhz machine than the crap of today. > > I think we should use ASCII graphics again. http://www.jfedor.org/aaquake2/ http://www.catb.org/~esr/jargon/html/T/troll.html > I think all the algorithms are crap, not useful at all. That's why research is done to invent better algorithms to solve real-world problems, you came to the right place if you want to share your knowledge. If the algorithms are so crap, what are you comparing them to, would be interesting to see some real alternatives. > Old programs on the IBM PC were much faster on a 4.77 Mhz machine than the crap of today. Naturally those programs were written for a 4.77 Mhz IBM PC. Put those amazing programs to a modern computer and the comparison is equally brutal the other way (the programs may be fast, but may lack tons of features and quality the applications which would be dead slow on that 4.77 Mhz machine, if they would run at all). On 2004-04-18, joe smith <rapu@ra73727uashduashfh.org> wrote: > >> I think all the algorithms are crap, not useful at all. > > That's why research is done to invent better algorithms to solve real-world > p...

Graphics--triangle intersection
Hi, I'm new to Mathematica. I would like to solve following problem. I have a number of overlapping triangles. In the intersection of all triangles, I want to draw the biggest triangle possible. Sounds simple ? Could this be solved in mathematica ? Any help is appreciated. Thanks Link to the forum page for this post: http://www.mathematica-users.org/webMathematica/wiki/wiki.jsp?pageName=Special:Forum_ViewTopic&pid=10465#p10465 Posted through http://www.mathematica-users.org [[postId=10465]] Hi, does the function imsConvexIntersect from http://www.im...

c++ graphic algorithm
Hi Would you introduce me a good c++ book about computer graphic with actual example, i am currently developing a GUI engine (like QT) for my operating system. A website would be appreciates thanks from Peter (cmk128@hotmail.com) cmk128@hotmail.com =E5=AF=AB=E9=81=93=EF=BC=9A > Hi > Would you introduce me a good c++ book about computer graphic with > actual example, i am currently developing a GUI engine (like QT) for my > operating system. > A website would be appreciates > thanks > from Peter (cmk128@hotmail.com) Hi I want a book that talk about image processing, like this: http://www.jhlabs.com/ip/filters/ thanks AGG http://www.antigrain.com/ ...

Rotated rectangles intersection algorithm... where?
Hi, I'm looking for an efficient algorithm to detect if two rectangles intersects. Rectangles can be rotated. Where can I find such an algorithm? Thanks in advance -- Faustino Dina -------------------------------------------------------- If my email address starts with two 'f' drop the first 'f' when mailing me. "Faustino Dina" <ffdina@matusa.com.mx> wrote in message news:2lgjb5FcdrgqU1@uni-berlin.de... > I'm looking for an efficient algorithm to detect if two rectangles > intersects. Rectangles can be rotated. Where can I find such an algorithm? http://www.magic-software.com/Intersection.html files WmlIntrBox2Box2.{h,cpp}. The algorithm used is the method of separating axes and tells you only if the rectangles intersect, not where they intersect. -- Dave Eberly http://www.magic-software.com ...

Linear Intersection Algorithm (Brandstein)
Hi, i'm developing the LI Algorithm in Matlab, it is used for audio source localization with array of microphones. Making a search on internet, i didn't find a lot about this. I read the original thesis and i'm working on it. My problem is now to understand what Lambda1k and Lambda2k coefficients means. To find those coefficients he used M1j(k) and M2j(k), and it tells that M1j(k) and M2j(k) are the DFT of the noises n1(l) and n2(l), now my question is, what does the "j" means in the M1j(k) and M2j(k)? Thank you very much! you should provide a link to a reference (i.e....

algorithmic and algorithm packages
Hi, In the framework of the algorithmic and algorithm packages, is it possible to "tune" the space between two consecutive lines of the produced algorithm ? Something like itemskip ? Thanks in advance, Vincent Kelner ...

A new algorithm for halfplane intersection
Dear All, I made a new algorithm for half-plane intersecting. My algorithm has a time complexity of O(NlogN) of course. But in comparison with previous algorithms(Divide-and-Conquer Algorithm) for the same purpose, my algorithm is easier to implement, easier to understand. I would like to know whether this algorithm is really new, and any comments you might have. My algorithm is as follows: definition of half-plane's polar angle: e.g. for the half-plane like x-y>=constant, we define its polar angle to 45 degrees. for the half-plane like x+y<=constant, we define its polar angle ...

the graphics and the concept of the graphic
Hiya all. everybody should applicate this type of guidelines This movement builds a strong visual link between the head and shoulders. If you get the correct relationship between the eyes, nose and mouth, you will end up with a good likeness. Our Pencil Portrait lesson explains and illustrates the step by step drawing techniques involved in creating the portrait of a young girl. At this stage, the drawing is no more than a set of carefully measured features that establish the final proportions of the portrait. There are three basic stages in the creation of the image...

Surface-Surface Intersection algorithm
Hi All, Does somebody knows what algorithm, the famous CAD/CAM packages do use for calculating surface-surface intersections. Many papers exists and most of them describe non efficient methods. We are looking for the standard method today used from commercial product. Any book / link to suggest us? Thanks so much, Alberto ...

paintComponent(Graphics graphics)
Hi=20 I hope I can explain this clearly without getting into too much detail as t= he code in question is a couple of thousand of lines. So to begin, I have = a JPanel to which I add JLabels and JComponents using JPanel's add() method= .. It works fine, but now I would like to print an image ON TOP of the adde= d JLabels and JComponents. For this I manipulate my JPanel's paintComponen= t(Graphics graphics) method. In it I have something of the following sort: paintComponent(Graphics graphics){ Graphics2D g =3D (Graphics2D)graphics.create(); g.drawImage(image, 200, ...

algorithm/algorithmic fonts
Hi, I'm using the 'algorithm' and 'algorithmic' packages. Some of the numbered lines have a variable-width sized font while other lines have a teletype font. Could someone pls inform me about how to change all the lines to the variable-width sized fonts. thx., glen Am 24.06.2010 14:13, schrieb John Smith: > Hi, > I'm using the 'algorithm' and 'algorithmic' packages. > Some of the numbered lines have a variable-width sized > font while other lines have a teletype font. Could > someone pls inform me about how to change all ...

graphic inside a graphic
Hi everyone Does anybody know how to insert a graphic inside a graphic?? I mean, to add a small graphic (as a zoom for example) inside a plot. Thanks augusto try axes try axes check out the tool 'imshow()', then try to bring the figure in shape get(gca) and superimpose your graph - 'hold on', 'plot()', 'hold off' (Haven't tried it my self so far) Thorben The example below shows you how to insert a graphic (e.g. photo) into another MATLAB figure. I = imread('peppers.png'); theta = linspace(-pi,pi,200); figure; plot(theta,cos(theta)); gr...

Graphics--combining graphics
I am trying to create an animation of a piecewise function. I have a graph of a ball rolling and I would like to combine an animation for one equation of motion for the first part with another equation for the second part of the motion. It is easy enough to create the two animations individually, however I am stumped on how to combine them into one continuous animation. Link to the forum page for this post: http://www.mathematica-users.org/webMathematica/wiki/wiki.jsp?pageName=Special:Forum_ViewTopic&pid=10007#p10007 Posted through http://www.mathematica-users.org [[postId=10007]] ...

Graphical Selection, Picking algorithm???
Google has failed me again. I don't even know what questions to ask. Pick up any cad program. Clicking on a line segment selects that segment. That's what I want to do. I have a Visual Basic 6/Win98SE program that takes gerber input and translates it to run a pen plotter. It also plots the "toolpath" on the screen. I'd like to be able to select a line segment and see the endpoint coordinates. The only thing I can think to do is try to construct a tiny window, redraw the graphic and somehow use the Windows API clipping functionality to tell me when a line passes thru the box. I'm not even sure this functionality exists. If I have to code it all in VB6, it's gonna be excruciatingly slow. There's gotta be a better way. Can someone point me to a methodology, an algorithm, tutorial, sample code, proper search terms, etc.? Thanks, mike -- Return address is VALID. 500MHz Tek DSOscilloscope TDS540 $2200 http://nm7u.tripod.com/homepage/te.html Wanted, 12.1" LCD for Gateway Solo 5300. Samsung LT121SU-121 Bunch of stuff For Sale and Wanted at the link below. http://www.geocities.com/SiliconValley/Monitor/4710/ mike <spamme0@netscape.net> wrote: > Google has failed me again. I don't even know what questions to ask. The term to search for is "pick correlation" --- the art of correlating a pick (an output position) back to the displayed graphical elements. > The only thing I can think to do is try to construc...

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

Who said that lockfree algorithms and waitfree algorithms and ,scalable algorithms are hard ?
Hello, Who said that lockfree algorithms and waitfree algorithms and scalable algorithms are hard ? as you have noticed i have tried to easy the job for you by inventing scalable algorithms and as you have noticed i have invented today a new algorithm of a very fast concurrent FIFO queue.. Here it is: http://pages.videotron.com/aminer/CQueue1.htm And i am right now thinking about my next invention , so stay tunned ! and enjoy all my programming inventions that you will find at: http://pages.videotron.com/aminer/ Thank you, Amine Moulay Ramdane. ...

Who said that lockfree algorithms and waitfree algorithms and ,scalable algorithms are hard ?
Hello, Who said that lockfree algorithms and waitfree algorithms and scalable algorithms are hard ? as you have noticed i have tried to easy the job for you by inventing scalable algorithms and as you have noticed i have invented today a new algorithm of a very fast concurrent FIFO queue.. Here it is: http://pages.videotron.com/aminer/CQueue1.htm And i am right now thinking about my next invention , so stay tunned ! and enjoy all my programming inventions that you will find at: http://pages.videotron.com/aminer/ Thank you, Amine Moulay Ramdane. ...

Who said that lockfree algorithms and waitfree algorithms and ,scalable algorithms are hard ?
Hello... Who said that lockfree algorithms and waitfree algorithms and scalable algorithms are hard ? as you have noticed i have tried to easy the job for you by inventing scalable algorithms and as you have noticed i have invented today a new algorithm of a very fast concurrent FIFO queue.. Here it is: http://pages.videotron.com/aminer/CQueue1.htm And i am right now thinking about my next invention , so stay tunned ! and enjoy all my programming inventions that you will find at: http://pages.videotron.com/aminer/ Thank you, Amine Moulay Ramdane. On Saturday, ...

C++ implementation of intersection search algorithms
Hi all. I have been using the books [1] Preparata & Shamos: "Computational Geometry" (1985) [2] de Berg & al: "Computational Geometry" (2000) to learn how to find the points of intersection among a set of line segments. While [2] gives a nice overview of the problem in entry-level terms, [1] gives some more insight into the technicalities and actual algorithms. However, neither text contains certain essential details - that I can find - that are required to actually implement the algorithm. The offending point is the status data structure termed L by [1, p. 282] and T by [2, p.25]. In [2], the data struture is loosely described as a "binary tree", while in [1] it is described as a "dicitionary". When I look up "dictionary" in the C++ literature, I am guided to the standard data structure std::map, which I happen to know is implemented as a binary tree. So far so good. The problem is that to actually implement the status data struture myself (I don't want to use libraries at this stage). I need to know what ordering criterion to use used internal to the status data structure. The key to the dictionay is that it is possible to compare two entries a an b using a '<' ordering operator; that is, to be able to evaluate the test a < b. The key to the intersection search algorithm is to swap the relative order of two elements a and b in the dictionary, at a point of intersection. Hence, the exact n...

algorithm for solving 4 intersecting spheres
Has anyone seen an algorithm that solves the point of 4 intersecting spheres? Where the inputs are four x y z points and their corresponding radii, and the output is a x y z coordinate. I have yet to find a nice chunk of code to do so yet. C or Java would be the best for me. Can anyone point (pardon the pun) me in the right direction? Thomas > Has anyone seen an algorithm that solves the point of 4 intersecting > spheres? Where the inputs are four x y z points and their corresponding > radii, and the output is a x y z coordinate. I have yet to find a nice chunk > of code to do so yet. C or Java would be the best for me. Can anyone point > (pardon the pun) me in the right direction? Four spheres are highly unlikely to intersect in a point. Assume you have three intersecting spheres not two of them the same. The intersection of two spheres is a circle. Intersecting this circle with a third sphere gives one or two points. Do you mean to find any point from the intersection of four balls (filled spheres)? -- Kalle Rutanen http://kaba.hilvi.org > Four spheres are highly unlikely to intersect in a point. Assume you > have three intersecting spheres not two of them the same. The > intersection of two spheres is a circle. Intersecting this circle with a > third sphere gives one or two points. > > Do you mean to find any point from the intersection of four balls > (filled spheres)? > In this case the spheres will interse...

A new algorithm for half-plane intersection
Dear All, I made a new algorithm for half-plane intersecting. My algorithm has a time complexity of O(NlogN) of course. But in comparison with previous algorithms(Divide-and-Conquer Algorithm) for the same purpose, my algorithm is easier to implement, easier to understand. I would like to know whether this algorithm is really new, and any comments you might have. My algorithm is as follows: definition of half-plane's polar angle: e.g. for the half-plane like x-y>=constant, we define its polar angle to 45 degrees. for the half-plane like x+y<=constant, we define its polar angle ...

I need graphics Brush/Pen algorithm
I need an algorithm which will compute a number of appropriate pen colors for a given background colour. I am using it for value based highlighting in a grid and whenever I chose a background color I have to go through a tedious process of choosing an appropriate pen color by trial and error. Are there any such algorithms? <mydejamail@yahoo.co.uk> wrote in message news:1140440430.975323.309150@g43g2000cwa.googlegroups.com... >I need an algorithm which will compute a number of appropriate pen > colors for a given background colour. > > I am using it for value based highlighting in a grid and whenever I > chose a background color I have to go through a tedious process of > choosing an appropriate pen color by trial and error. > > Are there any such algorithms? Aestethics aside, there are a number of things you could try to automate this. - inverting the color with XOR. Works well for light background (= dark pen) and dark bg (= light pen) but fails on medium tinted backgrounds. Worst cases would be medium gray (<=> medium gray!) and red <=> green. - fixed distance in RGB cube of 0.5 units. So (in RGB units of 0..255) RGB(0,0,0) would get a complementary color (128,128,128), RGB(200,0,64) would get (72,128,192). A distance of 0.5 is preferred because wrap-around of the values is necessary, so with a distance of 1 medium gray would still fail. - converting RGB to HSB and adjust the brightness up or down (e.g., if it is ...

Web resources about - Intersection of a hypersphere and a hyperplane - comp.graphics.algorithms

Intersection (set theory) - Wikipedia, the free encyclopedia
More generally, one can take the intersection of several sets at once. The intersection of A , B , C , and D , for example, is A ∩ B ∩ C ∩ D ...

The nonexistent intersection of the NFL's popularity and its violence - Grantland
Football is the most popular sport in America and probably the most dangerous. One has nothing to do with the other, and won't.

Cars Rush - The Road Traffic Intersection Run Hour Challenge on the App Store
Read reviews, compare customer ratings, see screenshots, and learn more about Cars Rush - The Road Traffic Intersection Run Hour Challenge. Download ...

Flickr: Intersection Consulting's Photostream
... and visual thinker that uses a casual, no-nonsense approach to help organizations achieve their goals using the dynamics of web 2.0 www.int ...

Richard Serra at MoMA - Intersection II (1992) - YouTube
Video walkthrough of Richard Serra's sculpture Intersection II (1992) on display at MoMA as part of the exhibition Richard Serra Sculpture: Forty ...

Left turn on red light allowed at more Brisbane intersections
Council has expanded the number of intersections at which drivers can turn left on red lights.

Boy killed video - Residents want intersection fixed, Kallangur
Residents at Kallangur urge authorities to "fix this intersection" after five-year-old Myles Sparling was killed while riding his bike with family. ...

This One Intersection Explains Why Housing Is So Expensive In San Francisco
San Francisco is a great place to live, if you can afford it.

The seven worst intersections for crashes in Victoria
Some people would never have a reason to call triple-0. Jason Stangherlin is sent scrambling to call emergency services at least once a month. ...

Woman killed after hit by car at major Gold Coast intersection - The Courier-Mail Search Search
A WOMAN has been killed after being hit by a car at a major Gold Coast intersection.

Resources last updated: 3/7/2016 8:09:25 PM