On points arranged in a parallelogram lattice, like on the image in this Wikipedia article, how to calculate the maximal distance any point on the plane may have to its closest point from the lattice. Or alternately, the maximal radius of a disk that can be placed on the plane such that it does not contain any point of the lattice.

As input I have the side length and both diagonals of one possible parallelogram that fits the lattice.

Edit: I meant the lattice not grid, i.e. only the sparse set of intersection points of a parallelogram grid.

  • $\begingroup$ Do you mean the "grid," the lines, or the "lattice," the intersection points of the lines? $\endgroup$ – Rory Daulton Jul 30 '15 at 12:40

Two vectors ${\bf a}$, ${\bf b}\in{\mathbb R}^2$ representing the sides of the given parallelogram determine the lattice $$\Lambda:={\mathbb Z}{\bf a}+{\mathbb Z}{\bf b}:=\bigl\{j {\bf a}+k {\bf b}\bigm| j, \ k\in{\mathbb Z}\bigr\}\ ,\tag{1}$$ but the representation $(1)$ of $\Lambda$ is not uniquely determined: The lattice ${\mathbb Z}^2$, for example, is generated by the pair $(1,0)$, $(0,1)$ as well as by the pair ${\bf a}:=(3,16)$, ${\bf b}:=(5,27)$.

In order to solve the problem at hand we have to determine a certain "standard presentation" of $\Lambda$: Find the shortest vector $${\bf p}=p\> {\bf u}, \quad |u|=1, \quad p>0,$$ occurring in $\Lambda$ (this is a standard problem in computational geometry). Then $\Lambda$ contains the one-dimensional lattice $\Lambda':={\mathbb Z}{\bf p}$, and is the union of translated copies of $\Lambda'$. Denote the distance between two successive such copies by $h>0$, and let ${\bf v}$ be a unit vector orthogonal to ${\bf u}$. There is a unique vector ${\bf q}\in\Lambda$ having a representation of the form $${\bf q}=c\>{\bf u}+h\>{\bf v}, \qquad 0\leq c<p\ ,$$ and $\Lambda$ can then be presented in the form $$\Lambda:={\mathbb Z}{\bf p}+{\mathbb Z}{\bf q}\ .$$ Let $\rho$ be the circumradius of the triangle with vertices ${\bf 0}$, ${\bf p}$, ${\bf q}$. Then any point ${\bf x}\in{\mathbb R}^2$ has a distance $\leq\rho$ from $\Lambda$, and there are points for which this bound is realized.

| cite | improve this answer | |
  • 1
    $\begingroup$ Drawing a picture made this so believable that I will refrain asking for a proof :-) $\endgroup$ – Jyrki Lahtonen Jul 30 '15 at 16:41

It is intuitively obvious that the point inside a parallelogram that is farthest from the sides is the center, the intersection of the two diagonals.

enter image description here

In my diagram, the center of parallelogram $ABCD$ is point $E$. The altitudes of triangles $ABE$ and $ADE$ (among others) gives the distance from the center to each of the parallelogram's sides. The altitude to the larger side is the smaller of these altitudes and gives your maximal distance from any point in the plane to its closest point on the grid.

You apparently know the side and diagonal lengths of the parallelogram. You can use Heron's formula to find the altitudes from that information. Let's say that the parallelogram's sides have lengths $a$ and $b$, with $a\ge b$, and the diagonals are $c$ and $d$. Then the triangle on the larger side has sides $a,\frac c2,\frac d2$. If we let

$$s=\frac{a+\frac c2+\frac d2}2$$

then the desired altitude is

$$\frac{2\sqrt{s(s-a)\left(s-\frac c2\right)\left(s-\frac d2\right)}}a$$

which is the answer to your question. Of course, you can simplify that expression in several ways. Note that you do not need the length of the shorter side of the parallelogram. Is that what you mean by "As input I have the side length and both diagonals..."?

| cite | improve this answer | |
  • $\begingroup$ The question was not about the distance to the side but to a grid point. That problem is further complicated by the fact that the closest point of the grid may not be a vertex of the parallelogram that the point falls in. As an example consider the grid consisting of translates of the parallelogram with side vectors $u=(5,6)$ and $v=(1,2)$, and the mid point of the parallelogram $P=(u+v)/2=(3,4)$. The grid point $(4,4)=u-v$ is much closer to $P$ than any of the vertices $(0,0), u,v,u+v$. $\endgroup$ – Jyrki Lahtonen Jul 30 '15 at 11:29
  • $\begingroup$ IOW there are many parallelograms giving the same lattice. $\endgroup$ – Jyrki Lahtonen Jul 30 '15 at 11:31
  • $\begingroup$ @JyrkiLahtonen: So by "the grid" you mean only the intersection points, i.e. the vertices of the parallelograms, rather than the grid lines? That does not match the usual English usage of the word "grid." (See here and here and here). You should probably re-word your question for clarity. $\endgroup$ – Rory Daulton Jul 30 '15 at 12:26
  • $\begingroup$ A good point, Rory! Somehow that did not occur to me. Let's wait for the original asker to comment what is intended. It would not be the first time that I am assuming a meaning I'm familiar with. To me it seemed that the OP is asking about the covering radius of the lattice. The Wikipedia page linked to by them does concentrate on the set of linear combinations with integer coefficients of the two sides of a fundamental parallelogram. $\endgroup$ – Jyrki Lahtonen Jul 30 '15 at 12:31
  • $\begingroup$ @JyrkiLahtonen: I just noticed that the OP uses the word "lattice" in the title and "grid" in the question, causing the confusion. So we are both right/wrong! $\endgroup$ – Rory Daulton Jul 30 '15 at 12:39

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.