|
|
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
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|