Title | ||
---|---|---|
Explicit and Efficient Formulas for the Lattice Point Count in Rational Polygons Using Dedekind--Rademacher Sums |
Abstract | ||
---|---|---|
We give explicit, polynomial-time computable formulas for the number of integer points in any two-dimensional rational polygon. A rational polygon is one whose vertices have rational coordinates. We find that the basic building blocks of our formulas are Dedekind--Rademacher sums , which are polynomial-time computable finite Fourier series. As a by-product we rederive a reciprocity law for these sums due to Gessel, which generalizes the reciprocity law for the classical Dedekind sums. In addition, our approach shows that Gessel's reciprocity law is a special case of the one for Dedekind--Rademacher sums, due to Rademacher. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/s00454-001-0082-3 | Discrete & Computational Geometry |
Field | DocType | Volume |
Integer,Reciprocity law,Topology,Combinatorics,Polygon,Vertex (geometry),Dedekind sum,Fourier series,Lattice (group),Mathematics,Dedekind cut | Journal | 27 |
Issue | ISSN | Citations |
4 | 0179-5376 | 5 |
PageRank | References | Authors |
0.60 | 3 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matthias Beck | 1 | 54 | 10.27 |
Robins | 2 | 38 | 6.97 |