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

Author

David Eppstein, Aug 15 2017

Keywords

• nonn

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A293596.

Formula

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

As Har-Peled and Lidicky (2013) proved, this sequence grows proportionally to n^{4/3}.