I've defined a new OEIS sequence but I'm having trouble figuring out a reasonable way to compute more terms.
Table read by rows: the $n$-th row gives the lexicographically earliest sequence of length $n$ such that the convex hull of $(1, a(1)), \ldots, (n, a(n))$ is an $n$-gon with minimum height.
The table begins:
$$\begin{array}{l} 1\\ 1,1\\ 1,1,2\\ 1,1,2,2\\ 1,1,3,2,3\\ 1,2,1,3,2,3\\ 1,3,1,4,4,2,3\\ 2,3,1,1,4,4,2,3\\ \end{array}$$
For example rows 5–8 are represented like this:
$$\begin{array}{ccccc|cccccc|ccccccc|cccccccc} 5\colon&&&&& 6\colon&&&&&& 7\colon&&&&&&& 8\colon&&&&&&&\\ & & & & & & & & & & & & & &.&.& & & & & & &.&.& &\\ & &.& &.& & & &.& &.& &.& & & & &.& &.& & & & & &.\\ & & &.& & &.& & &.& & & & & & &.& &.& & & & & &.&\\ .&.& & & &.& &.& & & &.& &.& & & & & & &.&.& & & &\\ \end{array}$$
By an exhaustiveness check, I've confirmed that the 9-gon in the ninth row must have a height greater than five, and I can construct one by hand with height six.
Any ideas on how to determine (or put a bound on) the minimum height required for the $n$-th row?
Any heuristics or tricks that can be used to compute more terms of the sequence? (for example, no value can appear more than twice in a single row.)
I have tried the following idea. At first we take a certain value $k$ of height to test whether it is reachable. Then like in Graham scan algorithm modification called Andrew's Monotone Chain Algorithm we will build lower and upper bounds of convex hull moving from left to right. Moving from left to right for each next point we take all possible $k$ variants, but move further to the right only if it is possible to add this point to either upper or lower bound without removing any other point from this bound. (There is a special case for the first and the last points which should be added to both lower and upper bounds.)
I've implemented this idea, it computed the first 16 rows in 38 seconds, took 687 more to compute the 17th row and 934 more to compute the 18th row.
$$\begin{array}{l|l} n & \pi_n \\\hline 2 & 1, 1 \\ 3 & 1, 1, 2 \\ 4 & 1, 1, 2, 2 \\ 5 & 1, 1, 3, 2, 3 \\ 6 & 1, 2, 1, 3, 2, 3 \\ 7 & 1, 3, 1, 4, 4, 2, 3 \\ 8 & 2, 3, 1, 1, 4, 4, 2, 3 \\ 9 & 1, 3, 4, 1, 5, 5, 2, 4, 3 \\ 10 & 3, 2, 4, 1, 1, 5, 5, 2, 4, 3 \\ 11 & 2, 1, 5, 6, 1, 7, 7, 2, 6, 3, 4 \\ 12 & 4, 3, 6, 2, 7, 7, 1, 1, 6, 2, 5, 4 \\ 13 & 2, 4, 1, 7, 8, 1, 9, 9, 2, 8, 3, 4, 6 \\ 14 & 4, 6, 7, 2, 8, 1, 1, 9, 9, 2, 8, 3, 4, 6 \\ 15 & 3, 5, 2, 8, 9, 1, 1, 11, 11, 2, 10, 3, 4, 8, 7 \\ 16 & 5, 4, 8, 9, 2, 10, 1, 1, 11, 11, 2, 10, 3, 4, 8, 7 \\ 17 & 4, 3, 8, 2, 11, 12, 1, 1, 14, 14, 2, 13, 3, 4, 11, 7, 9\\ 18 & 6, 8, 4, 11, 12, 2, 13, 1, 1, 14, 14, 2, 13, 3, 4, 11, 7, 9\\ 19 & 5, 4, 10, 12, 2, 15, 16, 1, 1, 17, 17, 2, 16, 3, 4, 14, 13, 8, 10\\ 20 & 8, 10, 5, 4, 14, 15, 2, 16, 1, 1, 17, 17, 2, 16, 3, 4, 14, 13, 8, 10\\ 21 & 7, 9, 4, 3, 14, 2, 17, 18, 1, 1, 20, 20, 2, 19, 3, 4, 17, 16, 8, 13, 11\\ 22 & 10, 8, 13, 5, 4, 17, 18, 2, 19, 1, 1, 20, 20, 2, 19, 3, 4, 17, 16, 8, 13, 11\\ \end{array}$$
Note that $h(11) - h(10) = h(13) - h(12) = h(15) - h(14) = 2$ and $h(17) - h(16) = 3$ where $h(n)$ is the minimum height of $n$-gon that indirectly confirms my conjecture about unlimited growth of $\frac{h(n)}n$.
Another interesting note is that $\pi_{n}$ has rather long common suffix with $\pi_{n - 1}$ for even $n$, with an exception of $n = 12$.
P. S. I would clarify in description of sequence that we need strictly convex polygon, because otherwise there is a trivial polygon of zero height.
P. P. S. It is easy to see that the sequence oeis.org/A156831 mentioned in comments counts identical permutation that gives degenerate convex hull however its perimeter contains all points.