3
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ 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 $\endgroup$ Nov 17, 2011 at 10:07
  • 1
    $\begingroup$ What do you mean by "the convex pentagon bounded by (all) the diagonals of P"? usually the do not bound a pentagon. $\endgroup$ Nov 17, 2011 at 11:41
  • $\begingroup$ Yes he does, in the first line. $\endgroup$
    – Igor Rivin
    Nov 17, 2011 at 13:10
  • $\begingroup$ @Fedor: Sorry, it should have read "the convex polygon bounded by all the diagonals of $\mathcal{P}$. $\endgroup$ Nov 17, 2011 at 15:23
  • 6
    $\begingroup$ 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... $\endgroup$ Nov 17, 2011 at 17:56

1 Answer 1

7
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ It seems that JOCG changed their website, the link in the post no longer works - this seems to be the new location: jocg.org/index.php/jocg/article/view/2969. (Of course, since full details are given in the answer, the paper can be easily found in many various places.) $\endgroup$ Jul 3, 2022 at 6:45
  • $\begingroup$ Thanks, I have updated the link in the answer (interestingly, they only changed the number in the end). $\endgroup$
    – Jan Kyncl
    Jul 4, 2022 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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