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.

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

Author

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

Keywords

• nice
• nonn

Comments

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

Examples

			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.
		

Links

• 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.

Crossrefs

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

Formula

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

Extensions

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