Partitioning a polygon into convex parts - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:18:56Z http://mathoverflow.net/feeds/question/60212 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60212/partitioning-a-polygon-into-convex-parts Partitioning a polygon into convex parts 565296944 2011-03-31T17:21:55Z 2011-03-31T18:12:36Z <p>I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.</p> <p>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.</p> <p>Can anyone point me to a source with a clear explanation of how to do this?</p> http://mathoverflow.net/questions/60212/partitioning-a-polygon-into-convex-parts/60215#60215 Answer by Joseph O'Rourke for Partitioning a polygon into convex parts Joseph O'Rourke 2011-03-31T17:38:33Z 2011-03-31T18:12:36Z <p>Chapter 2, Section 2.5 of <em><a href="http://cs.smith.edu/~orourke/books/compgeom.html" rel="nofollow">Computational Geometry in C</a></em> (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). <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/ChazelleConvexPartition.jpg" alt="Convex partition"></p> <p>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. </p> <p>Both Green's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the <a href="http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Partition_2/Chapter_main.html" rel="nofollow">"2D Polygon Partitioning"</a> section of the CGAL manual.</p>