Editing Polygon triangulation (section)

=== Monotone polygon triangulation ===
[[Image:Polygon-to-monotone.png|thumb|Breaking a polygon into monotone polygons]]

A simple polygon is monotone with respect to a line {{math|L}}, if any line orthogonal to {{math|L}} intersects the polygon at most twice. A monotone polygon can be split into two monotone ''chains''. A polygon that is monotone with respect to the y-axis is called ''y-monotone''. A monotone polygon with {{math|n}} vertices can be triangulated in {{math|O(<var>n</var>)}} time. Assuming a given polygon is y-monotone, the [[greedy algorithm]] begins by walking on one chain of the polygon from top to bottom while adding diagonals whenever it is possible.<ref name= bkos/> It is easy to see that the algorithm can be applied to any monotone polygon.