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

      0 references
      0 references
      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
      [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

      Identifiers