1
$\begingroup$

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.

  • 0
    Not sure if this is much help, but it could be possible to split the quadrilateral into two triangles and use Pick's theorem. http://en.wikipedia.org/wiki/Pick's_theorem (but this only works if the vertices of the quadrilateral are integer points.)2012-07-11
  • 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 1