2026-08-21T18:34:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27407 2026-08-21T14:42:38Z ddc:004 open_access

Counting All Lattice Rectangles in the Square Grid in Near-Linear Time Babichev, Dmitry Babichev, Sergey Lattice rectangles grid enumeration floor sums Möbius inversion We study the exact counting problem for all lattice rectangles contained in the square [0,n)×[0,n), including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction (u,v) and two side lengths, we derive a sequence of exact algorithms of complexity O(n²), O(n^{3/2} log n), O(n^{4/3} log n), and finally O(n log³n). The main idea behind the near-linear algorithm is to reduce the geometric summation to a constant-size family of weighted floor sums closed under Euclidean-style affine and reciprocal transformations, and hence evaluable in O(log n) time per query. The intermediate algorithms expose the structural reductions leading to this final kernel and provide independent cross-checks for the implementation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Babichev and Sergey Babichev 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.26 urn:nbn:de:0030-drops-274076 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.26 eng https://creativecommons.org/licenses/by/4.0/legalcode