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

%I #14 Oct 16 2017 02:12:01

%S 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,

%T 45,50,50,55,55,60,60,65,65,70,70,75,75,80,80,85,85,90,90,95,95,100,

%U 100,105,105,110,110,116,116,122,122,129,129,135,135

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

%C The convex layers of a point set are obtained by finding the convex hull, removing its vertices, and continuing recursively with the remaining points.

%C As can be seen in the subsequence 122, 129, 129, 135, the nonzero differences of consecutive sequence values do not grow monotonically.

%H S. Har-Peled and B. Lidicky, <a href="https://arxiv.org/abs/1302.3200">Peeling the grid</a>, arXiv:1302.3200 [cs.DM], 2013.

%H S. Har-Peled and B. Lidicky, <a href="https://doi.org/10.1137/120892660">Peeling the Grid</a>, SIAM J. Discrete Math., Vol. 27, No. 2 (2013), 650-655.

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

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

%e 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.

%Y Cf. A293596.

%K nonn

%O 1,3

%A _David Eppstein_, Aug 15 2017