I've just read The number of grid points near a circle.

I want to comment but I don't have the reputation so I have to post this as a question.

How do you prove that for each $x$ value less than $r\sqrt2/2$ there is a unique $y$ value and for each $y$ value less than $r\sqrt2/2$ there is a unique $x$ value?

My idea is that you could use the fact that the circle's gradient decreases from $0$ to $-1$ as $x$ goes from $0$ to $r\sqrt2/2$ and this implies that the line will not drop below one $y$ value for each $x$ value passed. However I can't think of how this can be formalized as a proof.

| cite | improve this question | | | | |

for each $x$ value less than $r\sqrt2/2$ there is a unique $y$ value

At a given position $0\le x\le\frac{r}{\sqrt 2}$, the point $(x,y)$ with

$$y = \left\lfloor\sqrt{r^2-x^2}\right\rfloor$$

is within the circle, and the point $(x, y+1)$ is outside. So the point must be counted.

Now about the uniqueness. Suppose there were a different point $(x,y')$ which should be counted as well. Since that point must lie inside the circle, it must satisfy $0\le y'<y$. You can now consider points around it. $(x,y'+1)$ will be inside since $y'+1\le y$ and $(x,y)$ is inside. $(x-1, y')$ must be inside since $(x,y')$ is inside and the circle and we are in the first quadrant. Likewise for $(x,y'-1)$. Both arguments will need discussion of a special case for $x=0$ resp. $y'=0$, but I'll leave that as an excercise for now.

So $(x+1,y')$ would be the most likely candidate for a point outside the circle. So let's see whether it can be outside the circle.

\begin{multline*} (x+1)^2+y'^2 \le (x+1)^2+(y-1)^2 = x^2+y^2 + 2x-2y+2 \\\le r^2+2x-2y+2 \le r^2+2(y-1)-2y+2 = r^2 \end{multline*}

There are three inequalities in there. The first is because $y'<y$, the second because $x^2+y^2\le r^2$ since $(x,y)$ is inside, and the third because $x<y$ since you are in the upper half of the first quadrant. The case of $x=y$ needs special treatment, but then $(x,y')$ would satisfy $x>y'$ and therefore already belong to the right half of the quadrant. Taken together, you have shown that $(x+1,y')$ cannot be outside the circle either, so $(x,y')$ will not be counted, so $(x,y)$ is unique for given $x$.

and for each $y$ value less than $r\sqrt2/2$ there is a unique $x$ value?

This is simply the same argument above, but with $x$ and $y$ changing their roles. So if you have one, you have both.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.