Put four lattice points inside a circle

Question

Given four lattice points and a radius $R$, I'd like to ask how to determine whether there exists a lattice point $P$ so that all four points fall in the circle with center $P$ and radius $R$?

Answer 1

Use Megiddo's algorithm to find the smallest circle encompassing the four points. Let this circle have center $(x,y)$ and radius $r$. If $r \gt R$, the circle you are looking for doesn't exist. Otherwise check whether a circle with radius $R$ centered at any of the four nearest lattice points surrounding $(x,y)$, encompasses all four points.