Here's a better search cutoff than the area bound, though I still
don't see how to make the search finite.
Theorem: Any convex lattice N-gon that contains K collinear lattice
points (x,y), (x+a,y+b), (x+2a,y+2b), ..., (x+(K-1)a,y+(K-1)b) has
area at least (K-1)(ceiling(N/2)-1)/2.
The proof relies on two lemmas that probably have better proofs than
these:
Lemma 1: If a and b are relatively prime integers, not both zero, then
the lines through lattice points in the direction of the vector (a,b)
are at a distance of 1/sqrt(a^2+b^2) from each other.
Proof: Take a square WXYZ with no lattice points on its boundary and
with WX a translate of the vector (a,b). Every line parallel to WX
passing through WXYZ that touches any lattice point must touch exactly
one lattice point in WXYZ. There are a^2+b^2 lattice points in WXYZ,
so that many lines, with a total separation of sqrt(a^2+b^2), so the
separation between any two is 1/sqrt(a^2+b^2) QED.
Lemma 2: Suppose a convex plane figure meets parallel lines R,S,T such
that the intersection with line R is a line segment of length X, and
lines S and T are at a distance of Y from each other. Then the area
of the figure is at least XY/2.
Proof: Let the intersection with line R be segment AB, and let C,D be
points in the figure on S,T respectively. Then by convexity the
figure contains triangles ABC and ABD. If R lies between S and T then
the triangles are disjoint and have total area XY/2. If R is outside
S and T then the larger triangle has total area greater than XY/2 QED.
Proof of theorem: Suppose the convex lattice N-gon contains K
collinear lattice points on a line parallel to vector (a,b), with a,b
relatively prime, not both zero. Consider the lattice lines parallel
to vector (a,b) that meet vertices of the N-gon. Since no more than
two vertices lie on any line, there are at least ceiling(N/2) such
lines. By Lemma 1, two of the lines must be at least
(ceiling(N/2)-1)/sqrt(a^2+b^2) apart. Furthermore, the line
containing the K collinear lattice points meets the N-gon in a segment
at least (K-1)sqrt(a^2+b^2) long. By Lemma 2, the N-gon has an area
of at least (K-1)(ceiling(N/2)-1)/2 QED.
In searching for an 11-gon of area less than 21.5, we can then rule
out any line of 9 collinear lattice points. Furthermore, once we have
two vertices X,Y of the polygon, lattice points ruled out by applying
the theorem to X will shadow other points from Y, which will be ruled
out by convexity, and those points may cast shadows from X, and so on.
Furthermore, any P for which the triangle PXY contains a prohibited
point will then be prohibited. If we can surround the partial polygon
with a ring of points that are angularly close, this will reduce the
problem to finitely many cases of choosing vertices from finite sets.
Unfortunately, I suspect this not is enough to make the whole problem
finite. Using Dylan's observation, it looks like we still have
infinitely many points to choose from for the third vertex (though I
haven't worked it out in detail). Still, we may be closing in on a
final answer to the problem.
Dan
