Computing All Lattice-Rectangle Counts by Rational Staircase Sums
2026-07-20 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors focus on counting all rectangles formed by points on an n-by-n grid, including those not aligned with the axes. They develop an efficient algorithm that computes these counts for all sizes up to N using advanced polynomial multiplication techniques. Their method involves careful mathematical steps like Möbius inversion and recursive computations, optimizing memory and operation counts. They also implemented and tested their algorithm against a slower, traditional approach to show its efficiency.
lattice pointsrectanglespolynomial multiplicationMöbius inversionnumber-theoretic transform (NTT)Chinese remainder theorem (CRT)divide-and-conquercoefficient extractionalgorithm complexityprefix sums
Authors
Dmitry Babichev, Denis Pinchuk
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 compute the complete table $F(1),\ldots,F(N)$ exactly in $O(M(N)\log N)$ coefficient-ring operations and $O(N\log N)$ ring elements of working memory, where $M(N)$ is a regular bound for multiplying degree-$N$ polynomials. The ring-level statement assumes that $6$ is invertible; over $\mathbb Z$ the only division is instead performed exactly in the elementary boundary term. With quasi-linear polynomial multiplication the arithmetic bound is $O(N\log^2 N)$. The algorithm applies a square-root cover before coefficient extraction and evaluates the resulting rational wedge and triangular sums by a local-denominator divide-and-conquer recursion. Primitive directions are recovered coefficientwise by Möbius inversion, followed by five prefix sums. A modular number-theoretic-transform (NTT) implementation with certified Chinese-remainder (CRT) recovery is evaluated experimentally against the $O(N^{3/2})$ all-values algorithm.