MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\mathcal{P}$ be a convex lattice polygon with $n$ vertices and let $\mathcal{L}$ be the set of all lattice points inside $\mathcal{P}$. For every $n \geq 5$, does there exist a point in $\mathcal{L}$ such that it also lies in the convex polygon bounded by (all) the diagonals of $\mathcal{P}$? How many such points are there? (//By diagonals I mean of course the lines different from the sidelines of the polygon which are connecting two vertices of $\mathcal{P}$.)

I proved a while ago that for $n=5$ there is such a point in $\mathcal{L}$. I also managed to show this now for $n \geq 6$ using a similar argument, yet it got more involved and I still need to check for potential bugs. Any ideas for the general case?

share|cite|improve this question
I suspect there are simple counterexamples for n=6, so I may be misunderstanding something. Can you say more about what interior region is supposed to have a lattice point? Gerhard "Ask Me About System Design" Paseman, 2011.11.17 – Gerhard Paseman Nov 17 '11 at 10:07
What do you mean by "the convex pentagon bounded by (all) the diagonals of P"? usually the do not bound a pentagon. – Fedor Petrov Nov 17 '11 at 11:41
Yes he does, in the first line. – Igor Rivin Nov 17 '11 at 13:10
Thanks, Igor, deleted my comment. – Joseph O'Rourke Nov 17 '11 at 13:22
I am still having difficulty understanding the phrase, "the convex polygon bounded by all the diagonals of $P$." In general, there is no convex polygon bounded by all the diagonals, if by "bounded" you mean, "forming the boundary of." There are many convex polygons, each bounded by a subset of the diagonals... – Joseph O'Rourke Nov 17 '11 at 17:56
up vote 3 down vote accepted

For $n=5$, this has been shown by Eppstein:
D. Eppstein, Happy endings for flip graphs, Journal of Computational Geometry 1 (2010), no. 1, 3--28.

For odd $n>5$, one could consider the polygon bounded by the longest diagonals.
It may be defined as the intersection of the half-planes containing $(n+1)/2$ vertices of $P$.
For $n=9$, this intersection may be empty (for example, if the nine vertices form three triples and each of the triples is placed very close to a vertex of a regular triangle).
For $n=7$, this intersection is non-empty. However, it may be free of lattice points: take, for example, the polygon $P$ with vertices $[0,1], [1,0], [2,0], [3,2], [3,3], [1,3], [0,2]$.

a lattice 7-gon with no lattice points in the inner polygon

share|cite|improve this answer

Your Answer


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.