Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Heza64

Circles!

This topic is 5645 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I''ve gotta question. On a normal grid, if the circles radius is from one point to another, can the circle''s edge touch more than 8 points? Like this: * O * O * O * * * O * * X * * O * * * O * O * O * The O''s are the points of the circle''s edge that touch a grid point. There are 8 in this circle. Can there ever be any more? Thanx Ian

Share this post


Link to post
Share on other sites
Advertisement
The question can be thought of also as this: How many unique pairs (x,y) exist such that x^2+y^2 = r^2. If there exists one pair (x,y), then there are 8 points: (x,y) (y,x) (-x,y) (-y,x) (x,-y) (y,-x) (-x,-y) (-y,-x). In the case of r = 5, the pair is (3,4). I think you are missing the "trivial" points of (0,5) (5,0) (0, -5) and (-5,0) So I find that 12 points exist. Im trying to find a proof that there exists only one unique pair (x,y) that satisfies the equation x^2 + y^2 = r^2, but haven''t really come across one yet. If you can prove that fact, then you prove the fact that there can only be at most 12 points.

Share this post


Link to post
Share on other sites
Well, if a circle has a radius of 5 and is centered at the origin then (5,0), (4,3), (3,4), (0,5), (-3,4), (-4,3), (-5,0), (-4,-3), (-3,-4), (0,-5), (3,-4) and (4,-3) are all points on the circle. Since that is 12 points I guess the answer is yes. I have no idea if there can be more than twelve. Certainly sine and cosine take on an infinite number of rational values and it seems unlikely that there are only 12 places where they are both rational at the same time, but it is beyond my limited knowledge of number theory to say whether or not they do.

I think you would need to qualify that with x, y and r are all rational as well since otherwise every point on a circle of radius r centered at the origin meets that condition.

[edited by - LilBudyWizer on January 29, 2003 5:37:20 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
There sure can be more than 12 points. For example, with r = 25 you have the points (0, 25) (7, 24) (15, 20) plus symmetry, and with r = 1105 you have (0, 1105) (47, 1104) (105, 1100) (169, 1092) (264, 1073) (272, 1071) (425, 1020) (468, 1001) (520, 975) (561, 952) (576, 943) (663, 884) (700, 855) (744, 817).

Share this post


Link to post
Share on other sites
The fact is that given x^2+y^2=r^2 there are an indefinite number of points on a circle unless the points are forced to be integral.

-- Exitus Acta Probat --

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
25 I knew out of my head. 1105 I wrote a couple of lines in Haskell to find.

Share this post


Link to post
Share on other sites
Fermat told us exactly which positive integers can be expressed as a sum of two squared integers. He left Gauss to provide a proof though, I think.

Firstly, if p is prime, then p is a sum of two squares if and only if p is NOT congruent to 3 modulo 4 (i.e. in C/C++, prime p is a sum of two squares if( p%4 != 3 ))

So 2 = 1*1 + 1*1, 5 = 1*1 + 2*2, but you can't express 3 as a sum of two squares. Primes can be expressed as a sum of two squares in essentially only one way (i.e. you could reverse the order of the addition (or negate one or both), but that is all).

If n is not prime, it is a sum of two squares if and only if, in the factorisation of n into prime factors, primes which are congruent to 3 modulo 4 occur only to EVEN powers. There will be several ways of expressing n as a sum of two squares.

The proof involves the use of Gaussian integers, i.e. complex numbers of the form w = x + iy with x,y integers and i = sqrt(-1). It's a fascinating topic though.



"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

[edited by - Paradigm Shifter on January 30, 2003 5:30:04 AM]

Share this post


Link to post
Share on other sites
Good old number theory that a highschooler shouldn''t be dwelving into. I wasn''t quite sure about that thing, I knew the Fermat had some role in it, and that Gauss (my favorite mathematician) finished things off. I ended up looking through my books and finding it. Is there any function that returns the number of integral pairs such that x^2 + y^2 = z? I would be interested in this. You could always brute force it, but thats not as much fun as the pure math aspect of it.

Brendan

Share this post


Link to post
Share on other sites
quote:
Original post by Paradigm Shifter
Firstly, if p is prime, then p is a sum of two squares if and only if p is NOT congruent to 3 modulo 4



Do you happen to know the name of this proof or (better yet) a place where the proof of this can be found? I have been looking off and on since last summer because I want to see if I can come up with an analogous theorem for 3 dimensions.



Qui fut tout, et qui ne fut rien
Invader''s Realm

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!