OFFSET
1,2
COMMENTS
Let P be a set of n points in the plane, no three of which are collinear, labeled by 1,2,...,n. A peeling sequence for P is any permutation of [n] that can be obtained by writing the labels of the points removed one by one. a(n) is the minimum number of such permutations that can be obtained, over all point sets of size n.
LINKS
Adrian Dumitrescu, Peeling sequences, Mathematics, 2022, 10, 4287; arXiv preprint, arXiv:2211.05968 [math.CO], 2022.
EXAMPLE
Let h denote the size of the convex hull of P.
The case n=3 is clear: there are 3!=6 permutations and each of them is a valid peeling sequence, so a(3)=6.
For n=4: If the points are in convex position, there are 4!=24 permutations. If the points are not in convex position, let 4 be the interior point. Then any permutation that starts with 4 is invalid, however, all remaining 4!-3!=18 permutations are valid. Thus a(4)=18.
For n=5: If h >= 4, there are at least 4*a(4) = 72 permutations. The case h=3 yields the smallest number, 24+18+18=60, of permutations; indeed, removing one of the extreme points yields a convex quadrilateral, while the other two removals can result in a triangle with a point inside. Thus a(5)=60.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Adrian Dumitrescu, Nov 04 2022
STATUS
approved