Approximating the Number of Lattice Points inside a Regular Polygon

Document Type : Research Paper


Department of Computer Science, University of Bojnord, Bojnord, Iran



We study the problem of counting the number of lattice points inside a regular polygon with $n$ sides when its center is at the origin and present an exact algorithm with $\mathcal{O}(k^{2}\log n)$ time and two approximate answers for this problem, where $k$ is the absolute value of side length of the minimum bounding box of the regular polygon. Numerical results show the efficiency of the approximations in calculating the answer to this problem.