## Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.

I know almost nothing about this subject, so I've been searching on Google Scholar and various computational geometry books, and I see a variety of different methods, some of which are extremely complicated (and meant to apply to non-simple polygons). I'm hoping there's a standard algorithm for this, with a clear explanation, but I don't know where to find it.

Can anyone point me to a source with a clear explanation of how to do this?

-
Triangulation is well-researched topic. For introduction see book by de Berg, Cheong, Kreveld Overmars. – Boris Bukh Mar 31 2011 at 17:30

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).