Return to Answer

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
                 

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Green's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Green's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
 

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Greene's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Greene's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
                

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Green's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Green's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
                

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Green's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Green's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
                Convex partition http://cs.smith.edu/%7Eorourke/MathOverflow/ChazelleConvexPartition.jpg

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Green's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Green's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
                

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Green's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Green's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.