|
%I #126 Oct 02 2023 04:44:02
%S 1,2,5,6,13,14,21,28,43,48,65,80,103,118,151,174,213,242,289,328,387,
%T 420,497,548,625,690,783,860,967,1046,1177,1264,1409,1498,1671,1780,
%U 1955,2078,2279,2444,2651,2824,3051,3240,3493,3676,3969,4176,4489,4714,5045,5302,5623,5906
%N a(n) is twice the least possible area enclosed by a convex lattice n-gon.
%C 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.
%C 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
%C From _Günter Rote_, Sep 18 2023: (Start)
%C 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.
%C 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)
%H Andrey Zabolotskiy, <a href="/A070911/b070911.txt">Table of n, a(n) for n = 3..150</a> (terms 3..102 from _Günter Rote_)
%H Imre Bárány and Norihide 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://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.
%H David Eppstein, Mark Overmars, Günter Rote, and Gerhard Woeginger, <a href="http://doi.org/10.1007/BF02187823">Finding minimum area k-gons</a>, Discr. Comput. Geom. 7 (1992), 45-58.
%H Steven R. Finch, <a href="/A249455/a249455.pdf">Convex Lattice Polygons</a>, December 18, 2003. [Cached copy, with permission of the author]
%H D. Olszewska, <a href="https://doi.org/10.1016/j.endm.2006.06.040">On the first unknown value of the function g(v)</a>, Electronic Notes in Discrete Mathematics, 24(2006), 181-185.
%H Hugo Pfoertner, <a href="/A321693/a321693_1.pdf">Illustrations of optimal polygons for n <= 26</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), pp. 85-88.
%H Günter Rote, <a href="/A070911/a070911_1.py.txt">Python program</a> for producing all optimal polygons
%H Günter Rote, <a href="/A070911/a070911_1.txt">Table of a(n), together with coordinates of smallest n-gons, for n=3..100</a>, (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.
%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)/2 = A063984(n) + n/2 - 1. [Simpson]
%F See Bárány and Tokushige for asymptotics.
%o See Code Golf StackExchange link, and the link to the Python program.
%Y See A089187 for the even-indexed subsequence. See A063984 for further information.
%Y Cf. A321693, A322029, A322106, A322107, A357888.
%K nice,nonn
%O 3,2
%A Pierre Bornsztein (pbornszt(AT)club-internet.fr), May 20 2002
%E Additional comments from _Steven Finch_, Dec 06 2003
%E a(11)-a(20) from _Hugo Pfoertner_, Nov 26 2018
%E a(21)-a(25) from _Hugo Pfoertner_, Dec 02 2018
%E 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
%E Data section cut at n=16 by _N. J. A. Sloane_, Dec 21 2022
%E a(17)-a(26) restored and a(27) onwards added by _Günter Rote_, Sep 18 2023
|
