Counting All Lattice Rectangles in the Square Grid in Near-Linear Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913079190618112 |
|---|---|
| author | Babichev, Dmitry Babichev, Sergey |
| author_facet | Babichev, Dmitry Babichev, Sergey |
| contents | We study the exact counting problem for all lattice rectangles contained in the square $[0,n)\times[0,n)$, including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction $(u,v)$ and two side lengths, we derive several exact algorithms: the classical $O(n^2)$ sweep, decompositions of complexity $O(n^{3/2}\log n)$ and $O(n^{4/3}\log n)$, a ten-moment weighted-floor-sum reduction of complexity $O(n\log^3 n)$, and a divisor-layer algorithm with the complexity $O(n\log^2 n)$. We also give an all-values algorithm that computes $F(1),\ldots,F(N)$ in $O(N^{3/2})$ arithmetic operations. The main idea behind the near-linear one-value algorithms is to reduce the geometric summation to constant-size families of weighted floor sums closed under Euclidean-style affine and reciprocal transformations. Besides the exact algorithmic results, we derive a two-term asymptotic expansion, $F(n)=\frac{4\log 2-1}{π^2}n^4\log n+B\,n^4+o(n^4)$ with the explicit formula for $B$, which provides an independent consistency check for the large-$n$ numerical data produced by the algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22456 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Counting All Lattice Rectangles in the Square Grid in Near-Linear Time Babichev, Dmitry Babichev, Sergey Computational Geometry 68W05, 68U05, 05B40 We study the exact counting problem for all lattice rectangles contained in the square $[0,n)\times[0,n)$, including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction $(u,v)$ and two side lengths, we derive several exact algorithms: the classical $O(n^2)$ sweep, decompositions of complexity $O(n^{3/2}\log n)$ and $O(n^{4/3}\log n)$, a ten-moment weighted-floor-sum reduction of complexity $O(n\log^3 n)$, and a divisor-layer algorithm with the complexity $O(n\log^2 n)$. We also give an all-values algorithm that computes $F(1),\ldots,F(N)$ in $O(N^{3/2})$ arithmetic operations. The main idea behind the near-linear one-value algorithms is to reduce the geometric summation to constant-size families of weighted floor sums closed under Euclidean-style affine and reciprocal transformations. Besides the exact algorithmic results, we derive a two-term asymptotic expansion, $F(n)=\frac{4\log 2-1}{π^2}n^4\log n+B\,n^4+o(n^4)$ with the explicit formula for $B$, which provides an independent consistency check for the large-$n$ numerical data produced by the algorithms. |
| title | Counting All Lattice Rectangles in the Square Grid in Near-Linear Time |
| topic | Computational Geometry 68W05, 68U05, 05B40 |
| url | https://arxiv.org/abs/2604.22456 |