Suppose you have a set of lattice points each of whose coordinates lie in the interval [0, *N*]. I've heard that the number of points on the convex hull is *O*(*N*^{2 / 3}). However, I cannot seem to be able to prove this. How can this be proven?

Also, how to generate testcases such that the convex hull contains as many points as possible?

I might have misunderstood, but if we take the 4 corner points (and have the remaining N-4 points inside), then their convex hull is a square with

O(N) lattice points on every edge...No, I mean the number of vertices of the convex hull. So, a square would only have four vertices.

A heuristic approach: take all the irreducible lattice vectors in [0,

a]^{2}for somea, and sort them by the angle. Now construct the lower right envelope by taking prefix sums of the sorted list of those vectors. Expected gain in bothxandycoordinate per point is Θ(a), and the number of vectors should be Θ(a^{2}). If you plug in , the last prefix sum is (Θ(N), Θ(N)), and the lower right envelope contains points.As for the other direction, it seems hard. I couldn't find a coherent proof for the 2-dimensional case on the Internet.

Nice, this allows us to construct testcases with

O(N^{2 / 3}) points on the hull.There's a paper in German ("Über die Gitterpunke auf konvexen Kurven" by Vojtěch Jarník) that proves a Θ(

l^{2 / 3}) bound for convexC^{1}curvesFof lengthlwith 0 ≤F' ≤ 1.If we have a convex polygon, we can draw a convex

C^{1}curve through all its vertices and apply his result to each octant. (The length of the curve isO(N).) This gives aO(N^{2 / 3}) bound for convex polygons.Edit: The paper also talks about convex polygons. One result is that the maximum number of vertices a convex polygon with integer coordinates and circumference

xcan have isNice to see a paper by Jarník cited, as someone whose head managed to collide with his books.

A simplified proof for the fact that a convex lattice polygon with coordinates in [0,

N] has at mostO(N^{2 / 3}) vertices:Let (

x_{0},y_{0}), ..., (x_{n},y_{n}) be the vertices with (x_{0},y_{0}) = (x_{n},y_{n}). Let (a_{i},b_{i}) = (x_{i + 1}-x_{i},y_{i + 1}-y_{i}) be thei-th line segment. W.l.o.g. let (a_{0},b_{0}), ..., (a_{k},b_{k}) be the line segments with 0 ≤a_{i}≤b_{i}(the ones in one octant). We'll only look at these segments. Note thatso there are at most

N^{2 / 3}indicesiwithb_{i}≥N^{1 / 3}. Let's call those segments long and the other ones short. Letm+ 1 be the number of short segments and (a_{sj},b_{sj}) be thej-th short segment. Thenso

On the other hand, by restriction on the octant and convexity of the polygon, the sequence is sorted, so using

a_{i}≤b_{i}we getso

m≤ 2N^{2 / 3}hencek≤ 3N^{2 / 3}. Summing up over all 8 octants, we get an upper bound of 24N^{2 / 3}for the number of vertices.Just FYI, in your first summation you probably want

y_{k + 1}-y_{k}.I assume you meant replacing

b_{k}byb_{i}and made the same error in your comment. That's correct. Thanks.Nice proof. But I think the sequence $$$a_{s_j} / b_{s_j}$$$ could always be sorted, which is independent of the restriction on the octant and convexity of the polygan?

If the polygon is not convex, then there can be duplicate $$$\frac{a_{s_j}}{b_{s_j}}$$$ and the proof falls apart.

If the polygon is not convex but you assume that no two sides are parallel, then yes, you can sort and do the same proof. Geometrically this corresponds to constructing a convex polygons with the same "side vectors". (The same idea applies if there is a constant $$$c$$$ such that every side is parallel to at most $$$c$$$ other sides.)