A063984 -id:A063984 - cp's OEIS frontend

A322343 Number of equivalence classes of convex lattice polygons of genus n.

16, 45, 120, 211, 403, 714, 1023, 1830, 2700, 3659, 6125, 8101, 11027, 17280, 21499, 28689, 43012, 52736, 68557, 97733, 117776, 152344, 209409, 248983, 319957, 420714, 497676, 641229, 813814, 957001, 1214030, 1525951, 1774058, 2228111, 2747973, 3184761

Offset: 1

Hugo Pfoertner, Dec 04 2018

nonn

			a(1) = 16 because there are 16 equivalence classes of lattice polygons having exactly 1 interior lattice point. See Pfoertner link.

Justus Springer, Table of n, a(n) for n = 1..60
Wouter Castryck, Moving Out the Edges of a Lattice Polygon, Discrete Comput. Geom., 47 (2012), p. 496-518, Column N in Table 1, p 512.
R. J. Koelman, The number of moduli families of curves on toric surfaces, Dissertation (1991), Chapter 4.2.
Hugo Pfoertner, Illustration of polygons of genus 1 representing the 16 equivalence classes, (2018).
B. Poonen and F. Rodriguez-Villegas, Lattice polygons and the number 12, Am. Math. Mon. 107 (2000), no. 3, 238-250 (2000).
Justus Springer, RationalPolygons.jl (Version 1.0.0) [Computer software], 2024.

Cf. A063984, A070911, A322344, A322345, A322346, A322347, A322348, A322349, A322350.

a(31) onwards from Justus Springer, Oct 25 2024

A070911 a(n) is twice the least possible area enclosed by a convex lattice n-gon.

Original entry on oeis.org

1, 2, 5, 6, 13, 14, 21, 28, 43, 48, 65, 80, 103, 118, 151, 174, 213, 242, 289, 328, 387, 420, 497, 548, 625, 690, 783, 860, 967, 1046, 1177, 1264, 1409, 1498, 1671, 1780, 1955, 2078, 2279, 2444, 2651, 2824, 3051, 3240, 3493, 3676, 3969, 4176, 4489, 4714, 5045, 5302, 5623, 5906

Offset: 3

Pierre Bornsztein (pbornszt(AT)club-internet.fr), May 20 2002

A convex lattice n-gon is a polygon whose n vertices are points on the integer lattice Z^2 and whose interior angles are strictly less than Pi.
For the even-indexed values, see A089187. The precisely known odd values were a(3)=1 (trivial), a(5)=5 and a(7)=13 (Arkinstall), a(9)=21 (Rabinowitz), a(11)=43 (Olszewska), a(13)=65 (Simpson), and a(15)=103 (Castryck). Additional values up to a(25) were first obtained as upper bounds "by massive calculations with several independent search programs" by Hugo Pfoertner. Pfoertner has made nice pictures of the best polygons he has found. See his link below. - Jamie Simpson, Dec 08 2022, adapted by Günter Rote, Sep 18 2023
From Günter Rote, Sep 18 2023: (Start)
The values a(n) can be computed in time polynomial in n by an algorithm of Eppstein, Overmars, Rote, and Woeginger from 1992: They showed how to compute the smallest convex n-gon in a set of N points in O(nN^3) time. The N points can be taken as an O(n^2) X O(n^2) grid: Each dimension of the bounding rectangle must be at least n/2, because a horizontal or vertical line can contain at most two vertices; since the area is known to be bounded by n^3, the other dimension cannot exceed 4n^2. In our case, the runtime can be reduced to O(nN^2), since the lowest vertex can be assumed to be a fixed point, say, the origin. By considering the lattice width, the grid can be reduced to size N=O(n^2) X O(n^1.5). Overall, this yields a theoretical runtime bound of O(n^8), for reporting all k-gons up to size n. This estimate agrees roughly with the observed runtimes in practice.
I have implemented the algorithm in Python and uploaded the program to the Code Golf Stackexchange site. It runs up to a(40) in a couple of minutes and produces some smallest polygon for each n. The values up to a(102) have been computed on a workstation in 31 hours. (End)

Andrey Zabolotskiy, Table of n, a(n) for n = 3..150 (terms 3..102 from _Günter Rote_)
Imre Bárány and Norihide Tokushige, The minimum area of convex lattice n-gons, Combinatorica, 24 (No. 2, 2004), 171-185.
Tian-Xin Cai, On the minimum area of convex lattice polygons, Taiwanese Journal of Mathematics, Vol 1, No 4 (1997).
W. Castryck, Moving Out the Edges of a Lattice Polygon, Discrete Comput. Geom., 47 (2012), pp. 496-518.
Code Golf StackExchange, The smallest area of a convex grid polygon, fastest-code challenge, started by Peter Kagey, Oct 22 2022.
David Eppstein, Mark Overmars, Günter Rote, and Gerhard Woeginger, Finding minimum area k-gons, Discr. Comput. Geom. 7 (1992), 45-58.
Steven R. Finch, Convex Lattice Polygons, December 18, 2003. [Cached copy, with permission of the author]
D. Olszewska, On the first unknown value of the function g(v), Electronic Notes in Discrete Mathematics, 24(2006), 181-185.
Hugo Pfoertner, Illustrations of optimal polygons for n <= 26, (2018).
S. Rabinowitz, O(n^3) bounds for the area of a convex lattice n-gon, Geombinatorics, vol.II, 4(1993), pp. 85-88.
Günter Rote, Python program for producing all optimal polygons
Günter Rote, Table of a(n), together with coordinates of smallest n-gons, for n=3..100, (2023). For some values of n, there are several polygons: From each equivalence class of smallest n-gons under affine lattice-preserving transformations, one representative is listed.
R. J. Simpson, Convex lattice polygons of minimum area, Bulletin of the Australian Math. Society, 42 (1990), pp. 353-367.

See A089187 for the even-indexed subsequence. See A063984 for further information.

Cf. A321693, A322029, A322106, A322107, A357888.

a(n)/2 = A063984(n) + n/2 - 1. [Simpson]

See Bárány and Tokushige for asymptotics.

Additional comments from Steven Finch, Dec 06 2003
a(11)-a(20) from Hugo Pfoertner, Nov 26 2018
a(21)-a(25) from Hugo Pfoertner, Dec 02 2018
a(13), a(26) and virtually all terms with even n up to a(42) (as given in A089187) go back to Jamie Simpson, Dec 07 2003
Data section cut at n=16 by N. J. A. Sloane, Dec 21 2022
a(17)-a(26) restored and a(27) onwards added by Günter Rote, Sep 18 2023

A322345 Maximal number of vertices of a convex lattice polygon containing n lattice points in its interior.

Original entry on oeis.org

4, 6, 6, 6, 8, 7, 8, 9, 8, 8, 10, 9, 9, 10, 10, 10, 10, 11, 10, 12, 12, 12, 11, 11, 12, 12, 12, 13, 12, 12, 13, 13, 13, 13, 14, 14, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 14, 15, 15, 15, 15, 15, 16, 15, 16, 15, 16, 16, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 16, 17, 17, 16, 17, 17

Offset: 0

Hugo Pfoertner, Dec 04 2018

nonn

This is an inverse of A063984 in the following sense: A063984(k) = min {n : a(n)>=k}. Thus a(n) grows roughly like const*n^(1/3). - Günter Rote, Sep 19 2023

Günter Rote, Table of n, a(n) for n = 0..200
Wouter Castryck, Moving Out the Edges of a Lattice Polygon, Discrete Comput. Geom., 47 (2012), p. 496-518, Column n_max in Table 1, p 512.
Wouter Castryck, Homepage. See the accompanying files for the above-referenced paper.
Günter Rote, Python program for this sequence and for A298562, (2023).
Günter Rote, Table of n, a(n) for n = 0..200 together with a corresponding a(n)-gon for each n, (2023).

Cf. A063984, A187015, A322343, A322346, A298562, A298755.

# See the Python program in the links section.

a(0) added by Andrey Zabolotskiy, Dec 29 2021
Name clarified by Günter Rote, Sep 18 2023
a(31) onwards from Günter Rote, Oct 01 2023

A089187 a(n) is the minimal area of a convex lattice polygon with 2n sides.

Original entry on oeis.org

1, 3, 7, 14, 24, 40, 59, 87, 121, 164, 210, 274, 345, 430, 523, 632, 749, 890, 1039, 1222, 1412, 1620, 1838, 2088, 2357, 2651, 2953, 3278, 3612, 4020, 4439, 4902, 5387, 5898, 6418, 6974, 7557, 8182, 8835, 9512, 10218, 10984, 11759, 12635, 13525, 14448, 15399, 16415, 17473, 18570

Offset: 2

Jamie Simpson, Dec 07 2003

nonn

For polygons with an odd number of sides see A070911.

			The first entry is 1 because the convex lattice quadrilateral of minimal area is a unit square. The minimal area hexagon has area 3.

Günter Rote, Table of n, a(n) for n = 2..100
Charles J. Colbourn and R. J. Simpson, A note on bounds on the minimum area of convex lattice polygons, Bull. Austral. Math. Soc., 45[1992], 237-240.
Stanley Rabinowitz, Convex Lattice Polygons, Ph.D. Dissertation (Polytechnic University, Brooklyn, New York, 1986).
Günter Rote, a(n), together with coordinates of some smallest 2n-gon, for n=2..100, (2023).
Günter Rote, Python program for this sequence, and for A070911, (2023).
R. J. Simpson, Convex lattice polygons of minimum area, Bull. Austral. Math. Soc., 42[1990], 353-367.

The even-indexed subsequence of A070911. See also A063984.

a(22) onwards from Günter Rote, Sep 17 2023

A322106 Numerator of the least possible squared diameter of an enclosing circle of a strictly convex lattice n-gon.

Original entry on oeis.org

2, 2, 50, 8, 10, 10, 1250, 29, 40, 40, 2738, 72, 82, 82, 176900, 17810, 1709690, 178, 11300, 260, 290, 290, 568690, 416, 2418050, 488, 3479450, 629, 2674061, 730

Offset: 3

Hugo Pfoertner, Nov 26 2018

If the smallest possible enclosing circle is essentially determined by 3 vertices of the polygon, the squared diameter may be rational and thus A322107(n) > 1.
The first difference of the sequences A321693(n) / A322029(n) from a(n) / A322107(n) occurs for n = 12.
The ratio (A321693(n)/A322029(n)) / (a(n)/A322107(n)) will grow for larger n due to the tendency of the minimum area polygons to approach elliptical shapes with increasing aspect ratio, whereas the polygons leading to small enclosing circles will approach circular shape.
For n>=19, polygons with different areas may fit into the enclosing circle of minimal diameter. See examples in pdf at Pfoertner link.

			By n-gon a convex lattice n-gon is meant, area is understood omitting the factor 1/2. The following picture shows a comparison between the minimum area polygon and the polygon fitting in the smallest possible enclosing circle for n=12:
.
    0 ----- 1 ----- 2 ------ 3 ------ 4 ------ 5 ------ 6
  6                          H ##### Gxh +++++ g
  |                     #        +      #    *   +
  |                 #       +              #        +
  |             #       +                 *   #        +
  5         I       i                          F        f
  |       #       +                    *        #       +
  |     #       +                                #      +
  |   #       +                     *             #     +
  4 J       j                                      #    e
  | #     @+                     *                  #  +
  | #     +      @                                   #+
  | #    +              @     *                      +#
  3 K   +                     @                     +   E
  |  # +                   *         @             +    #
  |   #                                    @      +     #
  |  + #                *                        +@     #
  2 k   #                                      d        D
  | +    #           *                       +        #
  | +     #                                +        #
  | +      #       *                    +         #
  1 l       L                         c        C
  |   +       # *                +        #
  |     +       #           +        #
  |       +  *    #     +        #
  0         a ++++ Axb ##### B
    0 ----- 1 ----- 2 ------ 3 ------ 4 ------ 5 ------ 6
.
The 12-gon ABCDEFGHIJKLA with area 52 fits into a circle of squared diameter 40, e.g. determined by the distance D - J, indicated by @@@. No convex 12-gon with a smaller enclosing circle exists. Therefore a(n) = 40 and A322107(12) = 1.
For comparison, the 12-gon abcdefghijkla with minimal area A070911(12) = 48 requires a larger enclosing circle with squared diameter A321693(12)/A322029(12) = 52/1, e.g. determined by the distance a - g, indicated by ***.

See A063984.

Hugo Pfoertner, Illustration of convex n-gons fitting into smallest circle, (2018).
Hugo Pfoertner, Illustration of convex n-gons fitting into smallest circle, n = 27..32, (2018).

Cf. A063984, A070911, A321693, A322029, A322107 (corresponding denominators).

a(27)-a(32) from Hugo Pfoertner, Dec 19 2018

A322107 Denominator of the least possible squared diameter of an enclosing circle of a strictly convex lattice n-gon. Numerators are A322106.

Original entry on oeis.org

1, 1, 9, 1, 1, 1, 49, 1, 1, 1, 49, 1, 1, 1, 1369, 121, 9801, 1, 49, 1, 1, 1, 1521, 1, 5329, 1, 5929, 1, 3844, 1

Offset: 3

Hugo Pfoertner, Nov 26 2018

			See A322106.

Cf. A063984, A070911, A321693, A322029, A322106.

a(27)-a(32) from Hugo Pfoertner, Dec 19 2018

A357888 a(n) is the minimal squared length of the longest side of a strictly convex grid n-gon of smallest area.

Original entry on oeis.org

2, 1, 2, 2, 5, 2, 5, 5, 5, 5, 10, 5, 10, 5, 13, 10, 13, 10, 13, 13, 17, 13, 17, 13, 25, 17, 25, 17, 25, 13, 25, 17, 26, 17, 26, 17, 26, 17, 26, 25, 26, 25, 29, 29, 29, 34, 34, 34, 41, 37, 41, 37, 41, 34, 41, 41, 41, 41, 41, 41, 61, 41, 61, 41, 61, 41, 61, 41, 41

Offset: 3

Hugo Pfoertner, Nov 10 2022

nonn

It is conjectured that at least one polygon of smallest area exists with 4 sides of length 1 for n >= 8 and additionally 4 sides of squared length 2 for n >= 12.

Code Golf StackExchange, The smallest area of a convex grid polygon, fastest-code challenge, started by Peter Kagey, Oct 22 2022.
User AlephAlpha in Code Golf StackExchange, The smallest area of a convex grid polygon (n=7 .. 37), results of computations, Nov 2022.
Hugo Pfoertner, Illustrations of optimal polygons for n <= 26 (2018).
Günter Rote, Python program

Cf. A063984, A070911, A089187, A321693, A322029, A322345, A322348.

Python
```
# See Rote link.
```

a(29)-a(60) from Günter Rote, Sep 20 2023

Terms a(61) and beyond from Andrey Zabolotskiy, Sep 21 2023

cp's OEIS Frontend

A322343 Number of equivalence classes of convex lattice polygons of genus n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A070911 a(n) is twice the least possible area enclosed by a convex lattice n-gon.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A322345 Maximal number of vertices of a convex lattice polygon containing n lattice points in its interior.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

A089187 a(n) is the minimal area of a convex lattice polygon with 2n sides.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A322106 Numerator of the least possible squared diameter of an enclosing circle of a strictly convex lattice n-gon.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A322107 Denominator of the least possible squared diameter of an enclosing circle of a strictly convex lattice n-gon. Numerators are A322106.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A357888 a(n) is the minimal squared length of the longest side of a strictly convex grid n-gon of smallest area.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions