That's a nice question and I like your conjectured possible form of a local condition. It reminds me of various theorems about convex sets such as [Helly's Theorem][1]. I think I can see that an ordered list of points are the vertices of a convex polygon (in clockwise order) exactly if your lists restricted to those points are the same list with a deletion. Given such a convex polygon we can also tell which points are inside it and which outside. I'd guess that $N=4$ is enough. Also that if one knows the lists for every $4$ point set then one can reconstruct all the convex polygons. That would seem to follow from [Cartheodory's Theorem][2].



  [1]: http://en.wikipedia.org/wiki/Helly's_theorem
  [2]: http://en.wikipedia.org/wiki/Carath%25C3%25A9odory%2527s_theorem_(convex_hull)