4
$\begingroup$

I have a graphic application to develop which involve many spheres. I should determine then on run time.

Supposing that I have a sphere of radius r, how can I determine the sub set of the sphere surface points that are integer?

E.g., $r = 10$ I can have $(10,0,0), (8,6,0),$ etc.

(Obs.: I really think this is not a programming question, that's why I not posted In stack overflow. If I am wrong, please fell free to warn me that :)

Pedro

  • 1
    You could just check the integer "grid" the sphere is in by using the formula of the sphere to see which points are on the surface of the sphere.2011-12-06
  • 1
    Ok, thats a alternative. But it results in a solution O(n³), which I am trying to avoid...2011-12-06
  • 1
    Have you seen [this](http://www.math.niu.edu/~rusin/known-math/95/three.sq)?2011-12-06
  • 0
    @PedroDusso by solving it for the third coordinate and only looking at points who have certain distance to the center you can easily make it quite faster than $\mathcal{O}(n^2)$.2011-12-06
  • 0
    See [this](http://www.dm.unito.it/~cerruti/ntlab2007/3squares-elementary.pdf) as well.2011-12-06
  • 1
    Obviously, there are no solutions if $r^2$ is not an integer. Are you assuming that $r$ is an integer?2011-12-06
  • 8
    See http://projecteuler.net/problem=3602011-12-08

1 Answers 1