Given a monotone polygon, with it's vertices given in counter-clockwise orientation, is there any fast process to determine whether the line between two vertices of that polygon A and B is a valid diagonal of that polygon? A valid diagonal is a line between those two vertices that lies inside the polygon and doesn't intersect or touch any edge of the polygon.Note : I need to be able to do this checking in constant time for triangulating the monotone polygon in linear time.
Determining whether a line between two points in a monotone polygon is a valid diagonal
computational geometry