Angle-Monotonicity of Delaunay Triangulation

Abstract Given an angle γ > 0 , a geometric path ( v 1 , … , v k ) is called angle-monotone with width γ if, for any two integers 1 ≤ i , j k , the angle between the two vectors v i v i + 1 → and v j v j + 1 → is at most γ. Let S be a set of n points in the plane. A geometric graph G with vertex set S is called angle-monotone with width γ, if there exists an angle-monotone path with width γ between every pair of vertices of G. In this paper, we show that the Delaunay triangulation of a given point set in the plane is not necessarily angle-monotone with width α, for 0 α 140 ∘ . This gives a negative answer to an open problem posed by Bonichon et al. (Bonichon et al., Gabriel triangulations and angle-monotone graphs: Local routing and recognition, Graph Drawing and Network Visualization, 2016).