

A290966


The number of convex layers in an n X n grid of points.


1



1, 1, 3, 3, 6, 6, 9, 9, 12, 12, 15, 15, 19, 19, 23, 23, 27, 27, 31, 31, 35, 35, 40, 40, 45, 45, 50, 50, 55, 55, 60, 60, 65, 65, 70, 70, 75, 75, 80, 80, 85, 85, 90, 90, 95, 95, 100, 100, 105, 105, 110, 110, 116, 116, 122, 122, 129, 129, 135, 135
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The convex layers of a point set are obtained by finding the convex hull, removing its vertices, and continuing recursively with the remaining points.
As can be seen in the subsequence 122, 129, 129, 135, the nonzero differences of consecutive sequence values do not grow monotonically.


LINKS

Table of n, a(n) for n=1..60.
S. HarPeled and B. Lidicky, Peeling the grid, arXiv:1302.3200 [cs.DM], 2013.
S. HarPeled and B. Lidicky, Peeling the Grid, SIAM J. Discrete Math., Vol. 27, No. 2 (2013), 650655.


FORMULA

For every n, a(2n) = a(2n1).
As HarPeled and Lidicky (2013) proved, this sequence grows proportionally to n^{4/3}.


EXAMPLE

For n=3, the a(3)=3 convex layers of a 3 X 3 grid are (1) the four corner points, (2) the four side midpoints, and (3) the center point.


CROSSREFS

Cf. A293596.
Sequence in context: A061795 A110261 A168237 * A049318 A325861 A079551
Adjacent sequences: A290963 A290964 A290965 * A290967 A290968 A290969


KEYWORD

nonn


AUTHOR

David Eppstein, Aug 15 2017


STATUS

approved



