Linear-time algorithms for weakly-monotone polygons (Q685601)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear-time algorithms for weakly-monotone polygons |
scientific article |
Statements
Linear-time algorithms for weakly-monotone polygons (English)
0 references
7 August 1994
0 references
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.
0 references
simple polygons
0 references
triangulation
0 references
linear-time algorithms
0 references