Given four points in $\mathbb{R}^2$, is there an efficient method to determine if the convex hull contains an integral point $(m,n)\in\mathbb{Z}^2$? If it helps, I can assume the convex hull is a quadrilateral.

  • $\begingroup$ Not sure if this is much help, but it could be possible to split the quadrilateral into two triangles and use Pick's theorem. en.wikipedia.org/wiki/Pick's_theorem (but this only works if the vertices of the quadrilateral are integer points.) $\endgroup$ – Old John Jul 11 '12 at 20:49
  • $\begingroup$ @OldJohn Yes thanks, but in my application the vertices will be general rational points. Raymond's reference below to Yanagisawa's paper might be helpful. $\endgroup$ – alex.jordan Jul 12 '12 at 2:20

Perhaps that this paper of Yanagisawa will help 'A Simple Algorithm for Lattice Point Counting in Rational Polygons'.

It begins with an historical overview with the important contributions of Pick and Barvinok (based on Ehrhart polynomials as you may find in his 'Lattice Points, Polyhedra, and Complexity') before proposing their own variant.

Hoping it helped a little,


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.