On the hyperbolicity of Delaunay triangulations

Abstract

If $ X $ is a geodesic metric space and $ x_1, x_2, x_3\in X $, a geodesic triangle $ T = \{x_1, x_2, x_3\} $ is the union of the three geodesics $ [x_1 x_2] $, $ [x_2 x_3] $ and $ [x_3 x_1] $ in $ X $. The space $ X $ is hyperbolic if there exists a constant $ \delta \ge 0 $ such that any side of any geodesic triangle in $ X $ is contained in the $ \delta $-neighborhood of the union of the two other sides. In this paper, we study the hyperbolicity of an important kind of Euclidean graphs called Delaunay triangulations. Furthermore, we characterize the Delaunay triangulations contained in the Euclidean plane that are hyperbolic.

Keywords

• delaunay triangulation
• voronoi graph
• hyperbolic graphs
• tessellation graphs