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

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

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. Har-Peled and B. Lidicky, Peeling the grid, arXiv:1302.3200 [cs.DM], 2013.

S. Har-Peled and B. Lidicky, Peeling the Grid, SIAM J. Discrete Math., Vol. 27, No. 2 (2013), 650-655.

Formula

For every n, a(2n) = a(2n-1).

As Har-Peled 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 A376449

Adjacent sequences: A290963 A290964 A290965 * A290967 A290968 A290969

Keyword

nonn

Author

David Eppstein, Aug 15 2017

Status

approved