Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
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.) – John Wordsworth Jul 11 '12 at 20:49
@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. – alex.jordan Jul 12 '12 at 2:20

1 Answer

up vote 3 down vote

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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