3
$\begingroup$

Let $r$ be a natural number, and consider the $\mathbb{Z}^2$ lattice points $S$ inside or on the circle $C$ of radius $r$ centered on the origin. Let $P$ be the convex hull of $S$; so $P$ is inscribed in $C$. I would like to "triangulate" $P$ in a special sense.

A triangulation of $P$ is a partition of $P$ into triangles whose interiors are pairwise disjoint, whose corners are points of $S$, and such that every point of $S$ is on the boundary of a triangle—either a corner or on the interior of an edge.

Define the weight of a triangulation of $P$ as the sum of the Euclidean lengths of the segments comprising the triangulation. (Each segment is counted once even if shared between two triangles.)

Q. What is the minimum weight triangulation of $P$ as a function of $r$?

For $r=1$, the shortest (minimum weight) triangulation has length $2 + 4 \sqrt{2} \approx 7.66$—a split diamond. But even for $r=2$, the minimum length is not obvious (to me). Here are four different triangulations for $r=2$ (where $S$ is a subset of a $5 \times 5$ grid) and their associated lengths. (Pardon any calculation errors.)


      5x5
      $r=2$:   $8+12 \sqrt{2} \approx 24.97$.
Below is just one triangulation for $r=3$, where $S$ is a subset of a $7 \times 7$ grid:
          7x7
          $r=3$:   $26+4 \sqrt{2}+8 \sqrt{5}+4 \sqrt{10} \approx 62.19$.
I am not seeing an obvious pattern. Has this been investigated in the literature? Are there at least asymptotic bounds?


Update (10Sep2018). Here are @WlodekKuperberg's shorter triangulations for $r=2,3$:
          WK


Update (11Sep2018). Here is one triangulation for $r=4$, in a $9 \times 9$ grid:


          9x9
          $r=4$:   $44+12 \sqrt{2}+8 \sqrt{5}+4 \sqrt{17} \approx 95.35$.


$\endgroup$
  • 3
    $\begingroup$ For $r=2$ there is a triangulation of weight $8(1+\sqrt{2})=19.3137\ldots$, namely consisting of the boundary of the large diamond plus its two diagonals. This is perhaps the best possible. $\endgroup$ – Wlodek Kuperberg Sep 9 '18 at 1:23
  • $\begingroup$ @WlodekKuperberg: Nice! $\endgroup$ – Joseph O'Rourke Sep 9 '18 at 1:50
  • $\begingroup$ Also, for $r=3$ there is a lighter triangulation, of weight $28+8(\sqrt{2}+\sqrt{5})=57.202\ldots$, consisting of the boundary of the octagon $P$, its vertical and horizontal diagonals, the boundary of the $4\times4$ square inscribed in $P$, and the square's diagonals. Perhaps some pattern begins to appear. $\endgroup$ – Wlodek Kuperberg Sep 9 '18 at 2:31
  • 1
    $\begingroup$ This can be still improved by removing four edges of length $1$ at the vertices of the octagon, reducing the weight to $53.202\ldots$. $\endgroup$ – Wlodek Kuperberg Sep 9 '18 at 13:13
4
$\begingroup$

The examples shown below for $\ $ $r=4,\ 5,\ $ and $\ 6\ $ illustrate the idea described in Dmitri's answer. Some modifications in the interior plus the choices of edges near the boundary of the circle are meant to lower the total weight of the edges. I do not claim that these triangulations are best possible - someone more computer-savvy should be able to verify it.


Wlodek


$r=$4:$\ \ \ w=44+22\sqrt2+8\sqrt5=93.00\ldots;$

$r=$5:$\ \ \ w=72+32\sqrt2+8\sqrt{10}=142.55\ldots;$

$r=$6:$\ \ \ w=88+32\sqrt2+7\sqrt{10}=192.49\ldots.$

Notice the ample (maximum possible) symmetry of the triangulation for $r=6$ and the surprisingly large number of the "good" $\{2$,$2$,$2\sqrt2\}$-triangles.

$\endgroup$
  • 1
    $\begingroup$ (I took the liberty of incorporating the image directly.) $\endgroup$ – Joseph O'Rourke Sep 20 '18 at 1:48
  • 1
    $\begingroup$ I am so impressed at your $r=4$ weight of $93$ undercutting my $95+$ that I will accept this even though it is not a complete answer. Thanks! $\endgroup$ – Joseph O'Rourke Oct 12 '18 at 22:18
  • $\begingroup$ Thanks Joe. Nice question, and an addictive one :) $\endgroup$ – Wlodek Kuperberg Oct 13 '18 at 0:56
7
$\begingroup$

I would like to propose a suggestion for finding some asymptotic bound, I think it should be $$\frac{1}{2}\cdot (2+\sqrt{2})\cdot \pi r^2.$$

Namely, the ratio of this number to the actual weight will tend to $1$ as $r\to \infty$.

To get this bound one needs to solve the following question:

Question. Find a triangle $\Delta$ with integer vertices that does not contain integer points in its interior and such that the following quantity attains its minimum: $$\lambda=\min_{\Delta}\left(\frac{{\rm Perimeter}(\Delta)}{{\rm Area}(\Delta)}\right).$$

I have a guess (should be super easy to prove/correct) that the minimum is $\lambda=2+\sqrt{2}$ and it is attained for the right angled triangle with a side of lenght $2$. In case this guess is not correct, one should replace in the above asymptotic the factor $2+\sqrt{2}$ by the correct value of $\lambda$.

I don't want to give a full proof of this asymptotic, but the idea is the following.

First, to construct a triangulation, we take the best triangle $\Delta$ that realises $\lambda$ and pave the plane by it in a standard way. This, of course will not quite pave the circle, but close to the boundary we change the triangulation so that it really triangulates everything.

The fact that we can not do better should follow from the fact that almost all sides of the triangulation - apart from the boundary ones belong to two triangles. This is why there is the factor $\frac{1}{2}$ in the beginning of the formula.

$\endgroup$
  • $\begingroup$ "and pave the plane by it": Nice idea to tile! $\endgroup$ – Joseph O'Rourke Sep 11 '18 at 14:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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