Counting Lattice Rectangles in $O(n\log n)$ Operations
2026-07-20 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study the problem of counting all rectangles formed by points on an n-by-n grid, including those not aligned with the grid axes. They present an exact algorithm that calculates this count more efficiently, running in about n log n steps instead of the previous n log squared n time. Their method breaks the problem into layers using number theory (Möbius layers) and cleverly reuses calculations with certain grid markers to save memory and time. They also implemented their solution in C++ and compared it experimentally to older algorithms. The approach involves advanced techniques like floor-moment queries and Euclidean recursion to achieve the speedup.
rectangle countinglattice pointsMöbius functionfloor-moment queriesEuclidean algorithmcoefficient conearithmetic complexityC++ implementationalgorithm optimizationinteger arithmetic
Authors
Dmitry Babichev, Tatiana Shpakova
Abstract
Let $F(n)$ be the number of rectangles, not necessarily axis-parallel, whose vertices belong to the $n\times n$ square grid of lattice points. We give an exact algorithm that computes one prescribed value $F(n)$ in $O(n\log n)$ arithmetic operations and $O(n^{3/4})$ arithmetic words of working memory. The algorithm decomposes the count into Möbius divisor layers, partitions weighted floor-moment queries by a truncated Euclidean coefficient-cone recursion, and reuses uniform marker grids along common coefficient paths. Each marker requires only its uniform cell and constant-size corrections at nearby boundaries, which select an exact precompiled cell operator. All integer operands have $O(\log n)$ bits. An exact 128-bit C++ implementation for the reported input range is compared experimentally with the previous $O(n\log^2 n)$ algorithm.