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.
Integral point inside a quadrilateral
1
$\begingroup$
geometry
integer-lattices
-
0@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. – 2012-07-12
1 Answers
3
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,