Lower Bounds on the Dilation of Plane Spanners

Publications

Lower Bounds on the Dilation of Plane Spanners

Author : Dr Anirban Ghosh

Year : 2016

Publisher : World Scientific Publishing Co. Pte Ltdwspc@wspc.com.sg

Source Title : International Journal of Computational Geometry and Applications

Document Type :

Abstract

(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 1 + (5 – 5)/2 = 2.1755⋯ 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.