Lattice spanners of low degree (Q2821117)

The authors consider plane geometric spanners of degree at most \(k\) for a point set \(P\). The minimum stretch factor on vertex set \(P\) is denoted by \(\delta_0(P,k)\). The following theorems are proved.NEWLINENEWLINETheorem 1. Let \(\Lambda\) be the infinite square lattice. Then, NEWLINE\[NEWLINE2.4142\dots=1+\sqrt 2\leq\delta_0(\Lambda,3)\leq(2\sqrt 2+3)5^{-\frac{1}{2}}=2.6065\dotsNEWLINE\]NEWLINE Theorem 2. Let \(\Lambda\) be the infinite square lattice. Then \(\delta_0(\Lambda,4)=\sqrt 2\).NEWLINENEWLINETheorem 3. Let \(\Lambda\) be the infinite hexagonal lattice. Then \(\delta_0(\Lambda,3)=1+\sqrt 3\).NEWLINENEWLINETheorem 4. Let \(\Lambda\) be the infinite hexagonal lattice. Then \(\delta_0(\Lambda,4)=2\).NEWLINENEWLINEAfter the interesting concluding remarks, important references can be found.