login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A070911 a(n) is twice the least possible area enclosed by a convex lattice n-gon. 9
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
3,2
COMMENTS
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)
LINKS
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.
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.
FORMULA
a(n)/2 = A063984(n) + n/2 - 1. [Simpson]
See Bárány and Tokushige for asymptotics.
PROG
See Code Golf StackExchange link, and the link to the Python program.
CROSSREFS
See A089187 for the even-indexed subsequence. See A063984 for further information.
Sequence in context: A069480 A354025 A100613 * A276082 A113240 A098376
KEYWORD
nice,nonn
AUTHOR
Pierre Bornsztein (pbornszt(AT)club-internet.fr), May 20 2002
EXTENSIONS
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:02 EDT 2024. Contains 371235 sequences. (Running on oeis4.)