DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.26

Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

Authors: Dmitry Babichev and Sergey Babichev

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

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.

Cite as

Dmitry Babichev and Sergey Babichev. Counting All Lattice Rectangles in the Square Grid in Near-Linear Time. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{babichev_et_al:LIPIcs.MFCS.2026.26,
  author =	{Babichev, Dmitry and Babichev, Sergey},
  title =	{{Counting All Lattice Rectangles in the Square Grid in Near-Linear Time}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.26},
  URN =		{urn:nbn:de:0030-drops-274076},
  doi =		{10.4230/LIPIcs.MFCS.2026.26},
  annote =	{Keywords: Lattice rectangles, grid enumeration, floor sums, M\"{o}bius inversion}
}

Search Results

Documents authored by Babichev, Sergey

Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message