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.

  • $\begingroup$ "of" what "triangle"? ​ ​ $\endgroup$ – user12859 Oct 28 '15 at 8:05
  • $\begingroup$ It should be 'that polygon' instead, edited that. $\endgroup$ – crysoberil Oct 28 '15 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.