Document Type : Research Paper

Author

• Mahdi Imanparast

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

Abstract

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.

Keywords

• Guass's circle problem
• lattice points
• regular polygons
• approximation algorithms