No label defined (Q3750120)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3986641
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3986641 |
Statements
1985
0 references
polynomial time
0 references
geometric complexity
0 references
decomposition of a simple polygon into a minimum number of convex polygons
0 references
optimal convex decomposition
0 references
Steiner points
0 references
dynamic programming
0 references
0.8388173580169678
0 references
0.8373821377754211
0 references
0.8373255729675293
0 references
0.8288406133651733
0 references
[For the entire collection see Zbl 0575.00022.] This contribution presents two algorithms for the decomposition of a simple polygon into a minimum number of convex polygons (the OCD problem \(=\) optimal convex decomposition). It is not without surprise that one makes the discovery that this problem is polynomial, and values this discovery accordingly. It is obvious that each vertex of a polygon displaying a reflex angle must be removed by the addition of a convex polygon to the decomposition, and at most two such vertices can be destroyed by this addition. The algorithms given by the authors circumvent the difficulty of having to introduce some interior Steiner points as vertices of the convex polygons generated, by considering particular patterns for which minimal decompositions can be generated, and which give the possibility of a dynamic programming approach. A basic \(O(n^ 6)\) algorithm is improved to an \(O(n+c^ 3)\) algorithm, where n is the number of vertices of the initial polygon, and c is the number of vertices which display a reflex angle.
0 references