2026/07/20 by Dmitry Babichev, Tatiana Shpakova · 1 citation
#cs.CG
Let F(n) be the number of rectangles, not necessarily axis-parallel, whose vertices belong to the n× n square grid of lattice points. We give an exact algorithm that computes one prescribed value F(n) in O(nlog n) arithmetic operations and O(n3/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(nlog2 n) algorithm.