Angle-monotonicity of Delaunay triangulation

摘要

Given an angle gamma 0, a geometric path (v(1), ... , v(k)) is called angle-monotone with width gamma if, for any two integers 1 <= i, j < k, the angle between the two vectors <(v(i) v(i+1))over right arrow> and (v(j) v(j+1)) over right arrow is at most gamma. 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 gamma, if there exists an angle-monotone path with width gamma 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 alpha, for 0 < alpha < 140 degrees. This gives a negative answer to an open problem posed by Bonichon et al. (2016) [14]. (c) 2020 Elsevier B.V. All rights reserved.