Determining whether a line between two points in a monotone polygon is a valid diagonal - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-21T23:53:31Z https://cs.stackexchange.com/feeds/question/48789 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/48789 2 Determining whether a line between two points in a monotone polygon is a valid diagonal crysoberil https://cs.stackexchange.com/users/41628 2015-10-28T03:57:55Z 2015-10-28T11:07:49Z <p>Given a <a href="https://en.wikipedia.org/wiki/Monotone_polygon" rel="nofollow">monotone polygon</a>, 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 <code>A</code> and <code>B</code> 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.</p> <p>Note : I need to be able to do this checking in constant time for triangulating the monotone polygon in linear time.</p>