2 deleted 1 character in body

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 trianglepolygon? 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.

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 triangle? 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.

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.

1

Determining whether a line between two points in a monotone polygon is a valid diagonal

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 triangle? 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.