A089187 -id:A089187 - cp's OEIS frontend

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

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

A063984 Minimal number of integer points in the Euclidean plane which are contained in the interior of any convex n-gon whose vertices have integer coordinates.

Original entry on oeis.org

0, 0, 1, 1, 4, 4, 7, 10, 17, 19, 27, 34, 45, 52, 68, 79, 98, 112, 135, 154, 183, 199, 237, 262, 300, 332, 378, 416, 469, 508, 573, 616, 688, 732, 818, 872, 959, 1020, 1120, 1202, 1305, 1391, 1504, 1598, 1724, 1815, 1961, 2064, 2220, 2332, 2497, 2625, 2785

Offset: 3

Pierre Bornsztein (pbornszt(AT)club-internet.fr), Sep 06 2001; May 20 2002

Consider convex lattice n-gons, that is, polygons whose n vertices are points on the integer lattice Z^2 and whose interior angles are strictly less than Pi. a(n) is the least possible number of lattice points in the interior of such an n-gon.
The result a(5) = 1 seems to be due to Ehrhart. Using Pick's formula, it is not difficult to prove that the determination of a(k) is equivalent to the determination of the minimal area of a convex k-gon whose vertices are lattice points.
Results before 2018 for odd n came from the following authors: a(3) (trivial), a(5) (Arkinstall), a(7) and a(9) (Rabinowitz), a(11) (Olszewska), a(13) (Simpson) and a(15) (Castryck). - Jamie Simpson, Oct 18 2022

			For example, every convex pentagon whose vertices are lattice points contains at least one lattice point and it is not difficult to construct such a pentagon with only one interior lattice point. Thus a(5) = 1.

I. Barany and N. 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, provides several programs.
C. J. Colbourn, R. J. Simpson, A note on bounds on the minimum area of convex lattice polygons, Bull. Austral. Math. Soc. 45 (1992) 237-240.
Steven R. Finch, Convex Lattice Polygons, December 18, 2003. [Cached copy, with permission of the author]
Hugo Pfoertner, Illustrations of optimal polygons for n <= 23, (2018).
S. Rabinowitz, O(n^3) bounds for the area of a convex lattice n-gon, Geombinatorics, vol. II, 4(1993), p. 85-88.
R. J. Simpson, Convex lattice polygons of minimum area, Bulletin of the Australian Math. Society, 42 (1990), pp. 353-367.

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

a(n) = A070911(n)/2 - n/2 + 1. [Simpson]
See Barany & Tokushige for asymptotics.
a(n) = min(g: A322345(g) >= n). - Andrey Zabolotskiy, Apr 23 2023

Additional comments from Steven Finch, Dec 06 2003
More terms from Matthias Henze, Jul 27 2015
a(17)-a(23) from Hugo Pfoertner, Nov 27 2018
a(24)-a(25) from Hugo Pfoertner, Dec 04 2018
a(26)-a(55) from and definition clarified by Günter Rote, Sep 19 2023

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

A365641 The minimum number of ways to label each triangle of a triangulation of an n-gon with one of its vertices so that different triangles get different labels (minimum taken over all triangulations).

Original entry on oeis.org

1, 3, 7, 14, 25, 41, 63, 92, 128, 173, 228, 293, 369, 458, 561, 676, 807, 955, 1119, 1300

Offset: 2

Günter Rote, Sep 14 2023

Originally proposed by Johan Wästlund, Aug 28 2007, as an equivalent formulation of A089187.

The "fan triangulations", where one vertex is connected to all other vertices, is optimal up to a(9). Starting from a(10)=128, other triangulations are better.

			a(4)=7. Suppose a 4-gon ABCD is triangulated with triangles ABC and ACD. If ABC is labeled B, then ACD can be given 3 possible labels, while if ABC is labeled A or C, only 2 labels are available for ACD and 3+2+2=7. - Johan Wästlund, Aug 28 2007

"""For a chosen "base edge" of a triangulated (n+2)-gon, (ul, ur, u2)
denotes the numbers of labelings where the left, the right, or
both vertices of the base edge have been used as labels.
The number of labelings where none of the basepoints is used is always 1.
tri[n] will contain the possible triplets (ul,ur,u2) for the
triangulations of an (n+2)-gon."""
tri = [{(0,0,0)}] # start with single edge (2-gon); no labels
def combine(u,v):
    (ul,ur,u2),(vl,vr,v2) = u,v # formula obtained by combining the cases
    return (1+vl+ur+ul, 1+vl+ur+vr, vr+ul+(ul+ur)*(vl+vr)+u2+v2 )
for n in range(1,18): # dynamic programming, requires large memory
    tri.append({combine(u,v) for k in range(n)
                for u in tri[k] for v in tri[n-k-1]})
print(", ".join(str(1+min(sum(t) for t in tr)) for tr in tri))

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A063984 Minimal number of integer points in the Euclidean plane which are contained in the interior of any convex n-gon whose vertices have integer coordinates.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A365641 The minimum number of ways to label each triangle of a triangulation of an n-gon with one of its vertices so that different triangles get different labels (minimum taken over all triangulations).

Views

Author

Keywords

Comments

Examples

Programs

Python