(I) We exhibit a set of 23 points in the plane that has dilation at least 1.4308,improving the previous best lower bound of 1.4161 for the worst-case dilation of plane spanners. (II) For every n ≥ 13, there exists an n-element point set S such that the degree 3 dilation of S equals 1 + √3 = 2.7321... in the domain of plane geometric spanners. In the same domain, we show that for every n ≥ 6, there exists a an n-element point set S such that the degree 4 dilation of S equals The previous best lower bound of 1.4161 holds for any degree. (III) For every n ≥ 6, there exists an n-element point set S such that the stretch factor of the greedy triangulation of S is at least 2.0268.
展开▼
