# Given a rectangle and a circle (having a lattice point as a center) find the number of lattice points of the rectangle inside the circle

The title explains the question easily. Also the radius of the circle is always an integer. The naive algorithm I thought was to check each and every lattice point of the rectangle but I wonder if we can solve it in less time complexity.

Here the lattice point means the simple integer point in 2D geometry plane

• I don't have a better worst case algorithm, but if you're aiming for a practical algorithm, a decent optimization would be to first intersect the square inscribed in the circle with the rectangle; that can be done in constant time and will give you a rectangle R. Then, in constant time you can find out how many lattice points are inside R. You'd still have to iterate over the rest of the points in the circle, but they're now less than half of the original amount. By decomposing the circle into more disjoint rectangles you can further optimize this strategy. Aug 5, 2021 at 17:08
• Bresenham to the rescue. Sep 5, 2021 at 3:32

The naive approach of checking every point in the rectangle would take $$\Theta(wh)$$ time, where $$w$$ is the width and $$h$$ is the height of the rectangle.
A moderate improvement on this is to scan every row (or column) of the rectangle and figure out where the circle starts and ends. Then, round up/down the circle endpoints, and simply subtract to know how many lattice points in the row lies in the circle. The time complexity is $$\Theta(\min(w, h))$$.
I would imagine that an excellent solution in $$\Theta(1)$$ time involves tricky algorithms and cases.