###First formulation: discrete geometry
Pick your favourite 2D square lattice (I'm sure we all have one...) and try to place n points 'in a circle' (that is: in general position [no 3 should be colinear] and forming the vertices of a convex polygon). Easy-peasy (assuming your favourite lattice is infinite- I know mine is). But now make your lattice smaller- finite even- say, $K \times K$- can you still do it? What is K is smaller? Bigger? Clearly the answer depends on n, so we ask:
What is the smallest $K=K(n)$ such that this can be done?
###Motivation?
This little problem- way out of my comfort zone in terms of field- was sort of inspired by this question. It initially looked like an interesting problem but, sadly, turned out to be rather trivial- putting points in a circle spelled trouble, it seemed, and I idly suggested a finite lattice to stop it happening- idle suggestion turned to idle speculation and I began to wonder how small the lattice had to be to stop the circle forming- beyond that, intrigue is the only reason why I am pursuing it.
So far my progress has been scant, but I have found a rather interesting reformulation: by focusing on the most densely populated 'quadrant' of the lattice and observing that the gradients of the edges within it must all differ. Modulo some suitable considerations of n mod 4 we can get-
###Reformulation: number theory
Given $\hat{n}$ what is the smallest $\hat{K}$ such that we may find $\hat{n}$ distinct fractions $\frac{p_1}{q_1},....\frac{p_n}{q_n}$ with $\Sigma_i q_i \leq \Sigma_i p_i = \hat{K}$?
Here $\hat{n}$ would be the number of points in the quadrant $\hat{K} \times \hat{K}$ the smallest size of that quadrant.
If we set $\hat{n}=\lceil \frac{n}{4} \rceil$, assume $\hat{K}=\frac{K}{2}$ and let the $p_i$, $q_i$ be the first $\hat{n}$ natural numbers we get a [really crappy] upper bound of $K \leq \lceil \frac{n}{4} \rceil (\lceil \frac{n}{4} \rceil +1)$- this fails to be sharp by the time n=5 for obvious reasons- 1) There has been no real consideration of the mod 4 behaviour and 2) By no means is this the most efficient way to make differing fractions.
Fixing 1) seems pretty easy (we can look at 2 different quadrants), but I didn't want to clog up the question with numerics when 2) is the real toughie. As mentioned above, I am neither a discrete geometer nor a number theorist, so this may unwind to be as trivial as the question that inspired it- still, to me it seems intriguing- and I am sufficiently invested to be hankering for an answer.
Edit: Gjergji's answer seems to be pretty great as a problem posed for polytopes, but I haven't accepted it yet because I am curious- can the number theory formulation do better? Is there a sharper result in that context?