1. perimeter/area = 2/inradius; so there is an equivalent formulation with "max min inradius($v_iv_jv_k$)". 2. Both quantities are constants. Wouldn't you rather know the value of those constants?

SOKOBAN is even PSPACE-complete, see J. Culberson, in: Proc. Int. Conf. on FUN with Algorithms, pp. 76-74, 1999) webdocs.cs.ualberta.ca/~joe/Preprints/Sokoban/index.html

Very nice! your upper bound is far too generous, if that is what you meant. The Hadamard bound gives $k^{3k/2}$.

@Lee, I don't get what you mean. By comparing sums or differences I understand something like $AB < AC-BD$. The OP does not talk about comparing the length $BD$ to the length $BD$ of another instance.

So $n$ varies from 0 to 6? Could you describe more precisely what you plotted there for $\alpha(n)$. I guess it is not easy to determine $\alpha(n)$.

A "given concrete Sokoban problem" can be always be solved in constant time. To meaningfully speak of polynomial time requires a problem with some inputs, some parameters, with an infinite family of instances.

There used to be an interesting answer posted here. Where is it? Was it wrong?

I wonder what the phrase "plus their adjacency relations" in the problem statement should mean. If if means that we know which of the distances represent edges, and which represent diagonals, then this example does not work.