<p>To complement David's answer: if $a$, $b$ and $r$ are all rational then the problem can be translated back to the integer case by multiplying by their common denominator; this may introduce false positives, but since there can be no more than $O(\log r)$ points on the circle then testing them all is no less efficient than the rest of the procedure.  And while David notes that the problem is at least as hard as factorization, it's basically exactly as hard as factorization: given a factorization of $r$, it's easy to find all the representations of $r$ as a sum of two squares.  First find all the representations of its factors $p=4n+1$ as a sum of two squares, then use the formula for expressing products of sums of two squares as a sum of two squares (along with the 'doubling formula') to find the rest.  As far as finding the representation(s) of a prime as a sum of two squares, you might want to see the discussions at <a href="https://stackoverflow.com/questions/5380323/whats-the-fastest-algorithm-to-represent-a-prime-as-sum-of-two-squares">https://stackoverflow.com/questions/5380323/whats-the-fastest-algorithm-to-represent-a-prime-as-sum-of-two-squares</a> and <a href="https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime">https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime</a> .</p>

CC BY-SA 3.0
2011-09-29T21:15:34.490Z
2011-09-29T21:15:34.490Z
2017-05-23T12:40:09.333Z
Steven Stadnicki
<p>If $a=b=0$ and $r=pq$ where $p$ and $q$ are primes congruent to 1 mod 4, then from the $O(1)$ integer points on the circle one could determine the factorization of $r$. So the problem is not going to be easier than factorization.</p>

CC BY-SA 3.0
2011-09-29T06:03:45.263Z
2011-09-29T06:03:45.263Z
David Eppstein
<p>Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The inputs $a, b, $ and $r$ are not necessarily integers. </p>

CC BY-SA 3.0
2011-09-29T00:06:15.670Z
I guess you meant $a$, $b$ and $r$.
Janoma
<cg.comp-geom>
Computing integer points on the circumference of a given circle
Ramzi
# Computing integer points on the circumference of a given circle

(Asked by: username_0 on 2011-09-28)

Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The inputs $a, b, $ and $r$ are not necessarily integers.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: I guess you meant $a$, $b$ and $r$.  

---

## 2 answers

### Answer by username_3 on 2011-09-29. Score: 11 | Accepted answer

If $a=b=0$ and $r=pq$ where $p$ and $q$ are primes congruent to 1 mod 4, then from the $O(1)$ integer points on the circle one could determine the factorization of $r$. So the problem is not going to be easier than factorization.


---

### Answer by username_2 on 2011-09-29. Score: 7

To complement David's answer: if $a$, $b$ and $r$ are all rational then the problem can be translated back to the integer case by multiplying by their common denominator; this may introduce false positives, but since there can be no more than $O(\log r)$ points on the circle then testing them all is no less efficient than the rest of the procedure. And while David notes that the problem is at least as hard as factorization, it's basically exactly as hard as factorization: given a factorization of $r$, it's easy to find all the representations of $r$ as a sum of two squares. First find all the representations of its factors $p=4n+1$ as a sum of two squares, then use the formula for expressing products of sums of two squares as a sum of two squares (along with the 'doubling formula') to find the rest. As far as finding the representation(s) of a prime as a sum of two squares, you might want to see the discussions at <https://stackoverflow.com/questions/5380323/whats-the-fastest-algorithm-to-represent-a-prime-as-sum-of-two-squares> and <https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime> .


---

