0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 5, 2021 at 17:08
  • $\begingroup$ Bresenham to the rescue. $\endgroup$
    – greybeard
    Sep 5, 2021 at 3:32

1 Answer 1

1
$\begingroup$

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.

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ An approximation is found in O(1) by dividing the area of the circular segment by that of a grid cell. An exact solution is still elusive. en.wikipedia.org/wiki/Gauss_circle_problem $\endgroup$
    – user16034
    May 4, 2022 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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