Smallest circle that intersects N number of points on the coordinate plane?

In the coordinate plane, there are special points that I am going to call grid points. These are the points whose x- and y-coordinates are both integers. If you were to draw a circle (centered on the origin), it is possible for this circle to intersect a certain number of grid points.

Usually, the circle will intersect 0 points. If you draw a circle of radius 2, it will intersect 4 points, which are on the axis lines. The radius of the circle does not have to be an integer, or even rational. The smallest circle that intersects 8 grid points has a radius of sqrt(5). It intersects the points (1,2), (-2,1), etc.

The smallest circle to intersect 12 grid points is the 3:4:5 Pythagorean triple. It intersects points like (0,5), (3,4), and (4,3).

One interesting fact is that due to the rotational symmetry of the coordinate plane, the number of intersected grid points will always be a multiple of 4.

—

My specific question is: What is the smallest circle that intersects at least 16 grid points?

As always, I like to generalize this. My broader question is: How would one find the smallest circle that intersects N number of points, where N is a multiple of four? Since I believe that this is an intrinsically hard problem, what are some good bounds for a solution?

—

I’ve been thinking about this for a while.

A (very easy) lower bound takes into account that at most two points can share the same y-coordinate (one point on each semicircle). This means that the radius must be at least N/4. For N=16, the lower bound is 4.

The upper bound for N=16 is a radius of 20, since that circle has 20 intersection points. Note that radius=20 may not be the smallest circle with 20 intersection points.

The problem is that this upper bound was not calculated directly from N; it required extra knowledge of circles that were bigger than it. It would be better if you only required knowledge of circles smaller than it.