|
%I #70 Sep 22 2023 08:54:55
%S 0,0,1,1,4,4,7,10,17,19,27,34,45,52,68,79,98,112,135,154,183,199,237,
%T 262,300,332,378,416,469,508,573,616,688,732,818,872,959,1020,1120,
%U 1202,1305,1391,1504,1598,1724,1815,1961,2064,2220,2332,2497,2625,2785
%N 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.
%C 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.
%C 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.
%C 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
%H I. Barany and N. Tokushige, <a href="http://www.renyi.hu/~barany/cikkek/94.pdf">The minimum area of convex lattice n-gons</a>, Combinatorica, 24 (No. 2, 2004), 171-185.
%H Tian-Xin Cai, <a href="https://doi.org/10.11650/twjm/1500406114">On the minimum area of convex lattice polygons</a>, Taiwanese Journal of Mathematics, Vol. 1, No. 4 (1997).
%H W. Castryck, <a href="http://dx.doi.org/10.1007/s00454-011-9376-2">Moving Out the Edges of a Lattice Polygon</a>, Discrete Comput. Geom., 47 (2012), pp. 496-518.
%H Code Golf StackExchange, <a href="https://codegolf.stackexchange.com/questions/253633/the-smallest-area-of-a-convex-grid-polygon">The smallest area of a convex grid polygon</a>, fastest-code challenge, started by Peter Kagey, Oct 22 2022, provides several programs.
%H C. J. Colbourn, R. J. Simpson, <a href="https://doi.org/10.1017/S0004972700030094">A note on bounds on the minimum area of convex lattice polygons</a>, Bull. Austral. Math. Soc. 45 (1992) 237-240.
%H Steven R. Finch, <a href="/A249455/a249455.pdf">Convex Lattice Polygons</a>, December 18, 2003. [Cached copy, with permission of the author]
%H Hugo Pfoertner, <a href="/A063984/a063984.pdf">Illustrations of optimal polygons for n <= 23</a>, (2018).
%H S. Rabinowitz, <a href="http://stanleyrabinowitz.com/bibliography/bounds.pdf">O(n^3) bounds for the area of a convex lattice n-gon</a>, Geombinatorics, vol. II, 4(1993), p. 85-88.
%H R. J. Simpson, <a href="http://dx.doi.org/10.1017/S0004972700028525">Convex lattice polygons of minimum area</a>, Bulletin of the Australian Math. Society, 42 (1990), pp. 353-367.
%F a(n) = A070911(n)/2 - n/2 + 1. [Simpson]
%F See Barany & Tokushige for asymptotics.
%F a(n) = min(g: A322345(g) >= n). - _Andrey Zabolotskiy_, Apr 23 2023
%e 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.
%Y Cf. A070911, A089187, A321693, A322029, A322345.
%K nice,nonn
%O 3,5
%A Pierre Bornsztein (pbornszt(AT)club-internet.fr), Sep 06 2001; May 20 2002
%E Additional comments from _Steven Finch_, Dec 06 2003
%E More terms from _Matthias Henze_, Jul 27 2015
%E a(17)-a(23) from _Hugo Pfoertner_, Nov 27 2018
%E a(24)-a(25) from _Hugo Pfoertner_, Dec 04 2018
%E a(26)-a(55) from and definition clarified by _Günter Rote_, Sep 19 2023
|
