Linear-time algorithms for weakly-monotone polygons (Q685601)

Triangulating a simple polygon is possible in linear time. But the corresponding algorithm is too complex to be considered practical. Simple optimal algorithms for special classes of polygons are interesting. The author studies a new class of so-called weakly-monotone polygons which contains the monotone class. The place in the hierarchy of simple polygons is discussed and a linear-time detection algorithm for the class is given. The author shows how to triangulate a weakly monotone polygon \(P\) in linear time, without prior knowledge of \(P\)'s weak-monotonicity. The algorithms are practical and conceptually simple.