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?

Improve this question
$\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$
    – Gerhard Paseman
    Commented 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$
    – Fedor Petrov
    Commented Nov 17, 2011 at 11:41
  • $\begingroup$ Yes he does, in the first line. $\endgroup$
    – Igor Rivin
    Commented 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$
    – Cosmin Pohoata
    Commented 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$
    – Joseph O'Rourke
    Commented Nov 17, 2011 at 17:56

1 Answer 1

Reset to default
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

Improve this answer
$\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$
    – Martin Sleziak
    Commented 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
    Commented Jul 4, 2022 at 0:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .