6
$\begingroup$

What is the minimal constant $\alpha$ so that for any convex lattice polygon $F$ there exists a lattice parallelogram $P\supseteq F$ of area $A(P)\leq \alpha\cdot A(F)$?

It is not hard to show that $\alpha\leq 4$ by the following argument (which I know for a long as it was some competition problem): let $AB$ be diameter of $F$ (or affine diameter), $C$ and $D$ be two vertices of $F$ most far from the line $AB$ in both half-planes, take $C\pm (A-B)$, $D\pm (A-B)$ as vertices of $P$. But I do not see why it is sharp nor how to strengthen it.

Improve this question
$\endgroup$
4
  • $\begingroup$ You can do the same with the constant $2$: Take the rightmost vertex of the shape and name it $A$ and take the leftmost, top and the lowest vertices and name them $C,D$ and $B$. Now draw two vertical lines the first one going from $A$ and the second from $C$ and draw two horizontal lines the first one going from $B$ and the second one from $D$. After drawing the lines we have a rectangle with area at most $2$ times of the main shape area, because the $ABCD$ is a quadrilateral with area at least $\frac{1}{2}$ of the rectangle and is contained in the main shape. $\endgroup$
    – Mohammad Ghiasi
    Commented Jun 22, 2015 at 4:47
  • 1
    $\begingroup$ @MohammadGhiasi but this rectangle may have non-integer vertices $\endgroup$
    – Fedor Petrov
    Commented Jun 23, 2015 at 4:14
  • $\begingroup$ I think which the vertices of the rectangle are lattice points because the drawn horizontal and vertical lines are lines from the grid. But maybe there is a misunderstanding between us(?). $\endgroup$
    – Mohammad Ghiasi
    Commented Jun 23, 2015 at 19:49
  • 1
    $\begingroup$ Ah, sorry, your construction has another problem: area of $ABCD$ may be much less then that of rectangle. $\endgroup$
    – Fedor Petrov
    Commented Jun 23, 2015 at 19:59

1 Answer 1

Reset to default
1
$\begingroup$

In this solution we wanna describe an algorithm which the $\alpha$ described in the problem is near $2$ for many shapes.

First Step) Insert your shape in a parallelogram (not necessary with vertices in grid). In order to do this it's enough to take the segment $AB$ which is equal with diameter of the shape and take vertices $C$ and $D$ from the vertices of the main shape in both sides of $AB$ which every one has maximal distance from $AB$. Now the bellow rectangle is a parallelogram contains the main shape and its area is at most two times of the main shape (because of the convexity of the main shape).

$\hspace{3.3cm}$enter image description here

Second Step) Now it's enough to find a parallelogram with vertices from the grid which is near the drawn rectangle good enough. For this, $8$ draw squares as shown in the bellow image in the corner of the rectangle. Obviously, there is at least one lattice point in every square (or on the boundary). Between the points are in squares $1,2,3$ and $4$ get the one with the highest distance from the line $L$. consider which this point is in $3$. Now find a lattice point in squares $6$ and $1$ which the first one is the square exactly behind $3$ and the second one is the square between $1,2,3$ and $4$ which is the farthest from $3$.

$\hspace{2cm}$enter image description here

Third Step) Now connect the grid points in the selected squares and complete the parallelogram. Because of the construction described in the above lines it's not hard to prove which the resulted parallelogram contains the rectangle.

$\hspace{2cm}$enter image description here

Finally, we have:

$$\frac{S_{\text{Main Shape}} }{S_{\text{Parallelogram} } } > \frac{\frac{1}{2} xy } {(x+2)(y+4)} $$

Which $x$ and $y$ are sides of the rectangle constructed in the first step and the above fraction is near $2$ if $x$ and $y$ are not near zero.

Improve this answer
$\endgroup$
2
  • $\begingroup$ well, it often happens that $x$ is less then 1/1000000 $\endgroup$
    – Fedor Petrov
    Commented Jun 24, 2015 at 14:14
  • $\begingroup$ Yes, I see. @FedorPetrov $\endgroup$
    – Mohammad Ghiasi
    Commented Jun 24, 2015 at 15:59

You must log in to answer this question.

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