Number of points on Convex hull with lattice points

Revision en1, by Anachor, 2018-10-03 01:35:18

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 at most O(N2 / 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?

Tags geometry, convex hull

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Anachor 2018-10-04 16:39:11 8 Tiny change: 'x hull is at most $O(N^{2/3' -> 'x hull is $O(N^{2/3'
en1 English Anachor 2018-10-03 01:35:18 400 Initial revision (published)