Number of points on Convex hull with lattice points

Правка en2, от Anachor, 2018-10-04 16:39:11

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(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?

Теги geometry, convex hull

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский Anachor 2018-10-03 01:35:18 400 Initial revision (published)