1
$\begingroup$

Another graduate student and I are working on an research project and are looking for a paper or other source that has a proof for a result about polygons on an integer lattice structure. Suppose you have a convex polygon on an integer lattice structure with more than 5 integer points on its boundary. Is there a way to take a subset of 5 of the integer points on the boundary of this polygon and connect any points not already adjacent to each other to form a smaller convex polygon, while guaranteeing you are not introducing new integer points on the boundary of this smaller convex polygon?

$\endgroup$
  • 2
    $\begingroup$ Just to understand what you mean: take the quadrilateral with the vertices $(2,0),(0,2),(-2,0),(-1,-1)$. Which points do you suggest to join? $\endgroup$ – fedja Oct 8 at 22:54
  • $\begingroup$ @fedja couldn't you just take $(-1,-1),(-2,0),(0,0),(1,0),(2,0)$? That's five integer points, they're all on the boundary of your polygon, and connecting them doesn't introduce any integer boundary points that weren't already on the boundary of your polygon? $\endgroup$ – Gerry Myerson Oct 9 at 11:58
  • 1
    $\begingroup$ @GerryMyerson It does not look like $(0,0)$ or $(1,0)$ is on the boundary to me, are they really? $\endgroup$ – fedja Oct 9 at 14:58
  • $\begingroup$ @fedja I think I mistook $(-1,-1)$ for $(-1,1)$. Sorry. $\endgroup$ – Gerry Myerson Oct 9 at 22:07
3
$\begingroup$

Consider the convex polygon with vertices $(0,0),(5,1),(4,4),(0,11),(-4,4),(-5,1)$. There are no lattice points on its boundary other than the six vertices. If you take any two that aren't adjacent, the line segment joining them has an interior lattice point, so if you take five of them, the segment joining the two that were adjacent to the one you leave out will contain a new lattice point on the boundary of the polygon formed by the five you take.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great answer! I made a picture for my own understanding, may I add it your answer? See here. $\endgroup$ – M. Winter Oct 9 at 12:46
  • $\begingroup$ Thank you @Gerry Myerson! This is very helpful for our search. $\endgroup$ – user6232872 Oct 9 at 18:10
  • $\begingroup$ And thanks @M. Winter for the picture! $\endgroup$ – user6232872 Oct 9 at 18:11
  • $\begingroup$ @M.Winter sure, go ahead. $\endgroup$ – Gerry Myerson Oct 9 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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