Lattice spanners of low degree

Publications

Lattice spanners of low degree

Author : Dr Anirban Ghosh

Year : 2016

Publisher : World Scientific

Source Title : Discrete Mathematics, Algorithms and Applications

Document Type :

Abstract

Let δ0(P,k) denote the degree k dilation of a point set P in the domain of plane geometric spanners. If A is the infinite square lattice, it is shown that 1 + 2 ≤ δ0(A, 3) ≤ (3 + 22)5-1/2 = 2.6065.. and δ0(A, 4) = 2. If A is the infinite hexagonal lattice, it is shown that δ0(A, 3) = 1 + 3 and δ0(A, 4) = 2. All our constructions are planar lattice tilings constrained to degree 3 or 4.