The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.11 Polygon Partitioning

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A polygon or polyhedron P.

Problem: How can P be partitioned into a small number of simple (typically convex) pieces?

Excerpt from The Algorithm Design Manual: Polygon partitioning is an important preprocessing step for many geometric algorithms, because most geometric problems are simpler and faster on convex objects than on nonconvex ones. We are better off whenever we can partition a nonconvex object into a small number of convex pieces, because it is easier to work with the pieces independently than with the original object.


  • GEOMPACK - triangulation and convex decomposition code (FORTRAN) (rating 8)
  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 7)
  • ParMetis 2.0 - A package for graph partitioning (C) (rating 4)

  • Recommended Books

    Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke Art Gallery Theorems and Algorithms by J. O'Rourke

    Related Problems

    Set Cover

    This page last modified on 2008-07-10 .